Experienced Optimization with Reusable Directional Model for Hyper-Parameter Search

1 Introduction

Machine leaning has become a main driving force for the development of artificial intelligence. Open source packages such as Weka [Hall et al., 2009] and Scikit-learn [Pedregosa et al., 2011] with a variety of learning algorithms provide users an easy way to apply machine learning. But the algorithm performance highly depends on the hyper-parameter setting. For example, the performance of neural network model is sensitive to the architecture, learning rate, and so on [Orr and M¨uller, 2012]. The hand-crafted hyper-parameter tuning requires expert domain knowledge and tremendous manpower. Thus, automatic machine leaning (autoML), with the aim of choosing the best hyper-parameter without human interference, is appealing. AutoML is usually studied as algorithm selection problems [Adankon and Cheriet, 2009; Biem, 2003; Brazdil et al., 2003], hyper-parameter tuning problems [Bengio, 2000; Bergstra and Bengio, 2012], and more recently, as the combined algorithm selection and hyper-parameter optimization problem (CASH) [Thornton et al., 2013; Feurer et al., 2015]. Despite the different formulations, derivative-free optimization methods are often employed to solve them. Unlike gradient-based optimization that relies on derivatives, these methods work through sampling from the search space. Derivative-free optimization has shown great potential in solving sophisticated problems, such as non-differentiable and non-convex functions.

∗This work is supported by the National Key R&D Program of China (2018YFB1004300), NSFC (61751306), Jiangsu SF (BK20160066), and Collaborative Innovation Center of Novel Software Technology and Industrialization. Yang Yu is the corresponding author.

However, derivative-free optimization commonly needs to sample a lot of hyper-parameters before finding a good one. This is due to the sampling nature of these methods, i.e., a sufficient exploration of the search space by many trial-anderrors is inevitable. The low sample efficiency issue is even severer in autoML tasks. Evaluation of a sampled hyperparameter in autoML is highly expensive because of, e.g., the high time consumption of the k-fold cross validation on large datasets. Therefore, improving the sample effectiveness of derivative-free optimization, and thus reducing the required sample amount, is a key issue for autoML.

In this paper, we propose an experienced optimization approach to improve the sample effectiveness, which extracts information from previous tasks to guide the optimization on new tasks. Although the tasks can be various, we observed that the search direction of different optimization processes can be aligned. Therefore, we propose to learn a directional model from a set of experienced optimization tasks, and reuse the directional model to guide the search in new optimization tasks. The directional model can help reduce unnecessary explorations and thus save wasted samples. We then incorporate the idea into the recently proposed derivative-free optimization method SRACOS [Hu et al., 2017], and implement the EXPSRACOS approach. Experiments on synthetic functions, hyper-parameter search for heterogeneous ensembles, and architecture design for deep neural networks disclose that the directional model can effectively capture the search direction information, and help EXPSRACOS improve the sample effectiveness significantly within limited sample budget.

2 Background

In this paper, we focus on the hyper-parameter optimization problems. Let C denote a machine learning model and δ ∈ ∆ denote a hyper-parameter setting, where ∆ is its hyper-parameter space. Taking k-fold cross validation as the evaluation criterion of Cδ , the evaluation can be formulated as follows:

where L(·) is a loss function, Di train and Divalid are the training and validation data in the i-th fold. The hyper-parameter optimization problem is to find the best hyper-parameter setting as δ∗ = argminδ∈∆ f(δ).

Since the hyper-parameter optimization objectives are often non-differentiable, they are commonly solved by derivative-free optimization. Derivative-free optimization is designed for sophisticated problems such as non-convex, non-continuous, and the like. We consider the minimization problems, and let X denote the compact searching space and f : X → R denote the objective function. The minimization problem can be presented as to find x∗ ∈ X s.t. ∀x ∈ X: f(x∗ ) ≤ f(x). The processes of derivative-free optimization algorithms [Shahriari et al., 2015; Munos, 2011; Yu et al., 2016] share the same idea of optimization from samples. Without any gradient information, derivative-free optimization explores objective space according to the samples and their evaluations. The most important part of derivativefree optimization is how to generate new samples. For example, Bayesian optimization [Shahriari et al., 2015] connects the searching space and the function values with a surrogate function modeled by the Gaussian process (GP), and chooses the sample with the best acquisition function value which is based on the GP model. However, autoML often faces integer and categorical searching spaces. SMAC [Hutter et al., 2011] was proposed to adapt this situation by replacing GP with the random forest model during building the surrogate function. SRACOS [Hu et al., 2017] is a recently proposed classification-based derivative-free optimization method. It shows outstanding efficiency and scalability in some applications

Employing derivative-free optimization approaches, autoML has achieved successful outcomes. AutoWeka and AutoSklearn, open source autoML projects using SMAC, have received outstanding performance in some autoML competitions. More recent studies focused on searching hyperparameters for deep neural networks. In [Baker et al., 2017], researchers employed deep reinforcement learning to model architecture designing process. The architectures of layers was considered as actions. The performance of designed architecture was considered as the reward. An reinforcement learning algorithm was then employed to train a policy to predict the actions.

Despite existing successes, evaluation of hyper-parameters in autoML tasks is commonly resource consuming, due to the large training data, repeated evaluations, large models, etc. To reduce the total sample cost, some previous studies have considered how to speed up the convergence by reusing the historical optimization experience for optimizing new tasks. Most of these studies are based on Bayesian optimization, e.g., [Swersky et al., 2013; Lindauer and Hutter, 2018]. To transfer the experience, the previous Bayesian process models can be directly reused into new optimization processes. For example, in [Lindauer and Hutter, 2018], historical models are linearly combined as a warmstart for new tasks. In our work, we don't reuse the historical optimization models directly as they may not be well aligned across different optimization tasks, instead, we learn and reuse a directional model for the optimization process that can be better aligned and transferable.

3 ProposedMethod

This section describes the proposed experienced optimization approach. We firstly present the overall framework, and then present the implementation details of this framework based on a state-of-the-art derivative-free optimization algorithm.

3.1 Overall Framework

This paper considers an optimization problem set F = {f}, where f ∼ F and F is an underlying problem distribution. For example, optimizing hyper-parameters for a certain learning model on different datasets can be seen as a problem distribution. Given Fe as the experienced problem set, the experienced optimization aims at optimizing future problems Ft = F - Fe more efficiently.

We have observed that, in different optimization processes, search direction can be aligned and can generalize across difference optimization processes. Therefore, our approach learns a directional model from the historical optimization processes, and guides new optimization processes.

The framework of the experienced optimization with directional model is presented in Algorithm 1. It mainly consists of three steps:

• Organizing the experience dataset DFe from the historical optimization processes (line 1 to 4). Derivative-free optimization methods often store some historical samples during optimization. The instances in DFe can be

Input:

• Fe, Ft: Experienced and target problem sets;
• A: The optimization approach;

Log&Assign: Log and assign experience dataset; Train: Train directional model.

Procedure:

• 1: DFe = ∅
• 2: for f ∈ Fe do
• 3: DfFe = Log&Assign(A, f)
• 4: DFe = DFe ∪DfFe
• 5: end for
• 6: Φ = Training(DFe )
• 7: for f ∈ Ft do
• 8: x∗f = A(f,Φ)
• 9: end for

Algorithm 1: Framework of Experienced Optimization by Directional Model extracted from the snippet of the stored samples. For each instance, we extract features and assign a label that is the direction to a later found better solution. In line 3, the Log&Assign sub-process is used to collect the labeled instances from the optimization processes.

• Learning directional model Φ on DFe (line 6). With the labeled experience dataset, training Φ is a supervised learning problem. Note that Φ can be trained by any state-of-the-art learning algorithm.
• Utilizing Φ to predict the direction of the next sample during optimizing in new problems (line 7 to 9). The directional models can be embedded in optimization method by adding a pre-sampling step, which generates a set of candidate samples. Among the candidate samples, the one most close to the direction predicted by Φ is selected as the next sample.

3.2 EXPSRACOS: Experienced SRACOS

We implement the idea within SRACOS, and propose the EXPSRACOS method for experienced optimization.

SRACOS. To explain EXPSRACOS clearly, it is necessary to introduce SRACOS briefly. SRACOS also follows the trialerror process. Throughout the optimization process, SRacos maintains two set of solutions B+ and B-. B+ contains the best k solutions, and B- contains a collection of the rest solutions. They are initialized from randomly sampled of solutions. In every iteration of SRACOS, it learns a classifier from B+ as the positive samples and B- as the negative samples. It then samples a new solution from the positive area of the classifier, and updates B+ or B- according to the evaluation result of the new solution. More details of SRACOS can be found in [Hu et al., 2017].

Collect experience dataset. We extract the experience dataset from SRACOS optimization processes on previous tasks. In the t-th iteration, the sampling area of SRACOS is learned on (x+t ,Bt ) during optimizing, where x+t ∈ B+ t . Bt stores the remaining solutions. Therefore, we organize the depending dataset (x+t ,Bt ) as a context matrix:

Note that κt is a m× n matrix, where m = |Bt | and n is dimension size of searching space. Each row of κt is a sample of Bt which is centralized around x+t . With the centralization, the search behavior at different time and in different optimization tasks can be aligned, thus the model trained on κ could be reused to other problems more easily.

Suppose x′t is the generated sample using the context matrix κt. We combine the two to compose an experience instance, [κt; x′t ]. We assign a label to this instance according to the quality of x′t . If it improves the objective value, the label is positive, otherwise, the label is negative, i.e.,

Input:

• f: Objective function to be minimized;
• P: The number of pre-sampling;
• r: The number of samples in initialization;
• N: The evaluation budget;
• Φ: Directional model;

Initialize: Initialization steps; Sample: Get a new sample by SRACOS.

Procedure:

1: (B+,B-, (˜x, ˜ y)) = Initialize(UX) 2: for t = r +1 to N do 3: P = ∅ 4: for i = 1 to P do 5: (κ, x) = Sample(B+, B-, λ, C) 6: p = Φ(κ, x) 7: P = P ∪ ((κ, x) , p) 8: end for 9: ((ˆκ, ˆx) , ˆ p) = argmax((κ,x),p)∈P p 10: ˆ y = f ( ˆx) 11: (B+,B-) = Update((ˆx, ˆ y) , B+, B-) 12: (˜x, ˜ y) = argmin(x,y)∈B+∪{( ˜x,˜ y)} y 13: end for 14: return (˜x, ˜ y)

where ˜ xt is the best-so-far solution. Putting all experience instances into a dataset, we obtain the experience dataset as DFe = {([κ1; x′1 ] , ℓ1) , ([κ2; x′2 ] , ℓ2) , . . . }.

Training directional model. Because the DFe is a labeled dataset, any classifier can be employed. From the previous subsection, we notice that an instance in DFe consists of two parts a matrix κ and a vector x′ . Thus, we should re-organize the instance from [κ; x′ ] by reshaping κ as a vector and combining it with x′ . In our work, we just apply a simple multilayer perceptron (MLP) as the directional model Φ. By the last layer of Φ, we map the directional model output to [0,1] to reflect the goodness of the sample.

EXPSRACOS. EXPSRACOS follows the algorithm framework of SRACOS. Before evaluating a sample, a presampling step is added. It generates a set of samples which will be filtered by the directional model. Algorithm 2 presents the pseudo code of EXPSRACOS. Line 1 is the initialization step. Line 4 to 8 is pre-sampling process. The directional model Φ will predict goodness of each pre-sampling solution (line 6). Only the solution with highest prediction will be evaluated (line 9 and 10). And then the solution and its evaluation value will be used to update (B+,B-). An implementation of EXPSRACOS can be found at https: //github.com/eyounx/ExpSRacos.

Why EXPSRACOS works. We discuss why experienced optimization works under the following two assumptions:

• We assume that optimization tasks f ∈ Fe and Ft share the same search space X;
• For any two instances ([κa; x′a ] , ℓa) and ([κb; x′b] , ℓb) in DFe , we assume ℓa = ℓb if [κa; x′a ] = [κb; x′b].

The centralization process of κ makes sure that the second assumption can be met in most cases. The directional model Φ of historical optimization processes is to predict whether new sample x is good. Based on these two assumptions, Φ can be reused to predict the goodness of new samples on new tasks. In EXPSRACOS, only the sample with the highest prediction of Φ will be evaluated. Compared with SRACOS that wastes many samples for exploration, EXPSRACOS avoids evaluating many inferior samples.

4 Experiments

In this section, we empirically investigate the effectiveness of the proposed experienced optimization framework (using its implementation EXPSRACOS) on some tasks. We firstly study EXPSRACOS on a synthetic function. Then, EXPSRACOS is employed to tackle two autoML tasks, tuning hyperparameters on ensemble classifier and optimizing architecture of deep neural network. In these tasks, the directional models are all structures of MLP. But the detail settings are slightly different according to tasks.

We choose the state-of-the-art derivative-free optimization methods to compare with EXPSRACOS including SRACOS (code from https://github.com/eyounx/ZOOpt), CMAES [Hansen et al., 2003] (code from https: //pypi.python.org/pypi/cma), SMAC (code from https://github.com/automl/SMAC3) and TPE [Bergstra et al., 2011] (code from http: //jaberg.github.io/hyperopt/).

4.1 On Synthetic Functions

We firstly compare EXPSRACOS with SRACOS, CMAES, SMAC and TPE on a highly non-convex function Ackley: f(x) = -20e(- 1 5 √ 1n ∑ni=1 (xi-x∗i )2 ) - e 1n ∑ni=1 cos 2π(xi-x∗i ) + e + 20. x∗ = (x∗1 , x∗2 , . . . , x∗n ) denotes the optimal solution, where n is dimension size. The search domain is X = [-1, 1]n . Because Ackley function has many local optima, it provides an extreme situation to test the effectiveness of the experienced optimization.

Problem settings. The problem distribution F is constructed by randomly shifting x∗ of Ackley function. The relationship among different functions depends on the size of the space Xshift . If it defines a tiny space, problems are more similar with each other. We investigate how Xshift influences the performance of EXPSRACOS by setting Xshift = [-0.1, 0.1]n and [-0.5, 0.5]n , where we set n = 10 and 20.

Considering combination, there are 4 different problem distributions on synthetic function experiments.

Training Φ for EXPSRACOS. For each Xshift setting, we sample a batch of problems to form Fe and Ft, where Fe ∩ Ft = ∅. Because Xshift = [-0.5, 0.5]n is much larger than Xshift = [-0.1, 0.1]n , we set |Fe| = 200 for [-0.1, 0.1]n and |Fe| = 400 for [-0.5, 0.5]n . We collect experience dataset DFe by applying SRACOS to optimize f ∈ Fe with 400 evaluation budget and repeat running for 5 times. We set |Ft| = 100 target problems for all 4 settings. Because of the inferior sample effectiveness of SRACOS, the dataset DFe is highly imbalanced in classes. The number of positive instances is much less than negative instances. The upsampling strategy is used to adjust the balance, on which the directional model is trained.

On convergence rate. We test the convergence rate of each method on Ackley with a specific optimal solution x∗ and the budget of 100 samples. We set x∗ = (0.2, 0.2, . . . ) for Xshift = [-0.5, 0.5]n and x∗ = (0.04, 0.04, . . . ) for Xshift = [-0.1, 0.1]n . Ackley functions with these two x∗ are not in Fe, so it can verify the transfer performance of Φ for each problem distribution. Each method runs for five times independently on each function. In Figure 1, two settings of the optimal solutions are presented. It can be observed that the reuse of the directional model is generally less affective for the larger change of the optimal solution. Meanwhile, the convergence speed of EXPSRACOS is the fastest on all settings. Especially compared with SRACOS, in Figure 1 (a), (b), the convergence of EXPSRACOS is significantly faster.

On average performance. We report the average performance of the compared methods on all problems in Ft with 50 evaluation budget. Each method runs five times on each problem independently. The average performance is presented in Table 1. EXPSRACOS shows the best performance among all problem settings. The conclusion of this experiment is similar with that of the convergence experiment. EXPSRACOS is much better than the compared methods when shifting space Xshift is small, but gets smaller advantage for larger shifts.

The results of synthetic function experiments indicate that the experienced optimization mechanism can have significantly improved performance when problems are similar.

4.2 On AutoML Tasks

In this section, we apply EXPSRACOS to solve autoML tasks: the hyper-parameter optimization on heterogeneous weighted voting ensemble classifier and the architecture optimization on deep neural networks. These two tasks with the k-fold cross validation error as the criterion have been formulated in Section 2. For EXPSRACOS, the datasets are split as source and target datasets. We organize the experience dataset on source datasets, and test the reusing performance of Φ on the target datasets. EXPSRACOS is compared with SRACOS, SMAC, TPE. In the experiment results, the optimization and generalization performance mean the validation error on training dataset when optimization and test error on testing dataset. We run each method for 3 times independently and the best solution is selected for testing generalization performance. For each optimal solution, we test the generalization performance for 5 times and report its average performance.

On Ensemble Classifier Hyper-Parameter Optimization

This task is optimizing hyper-parameters for heterogeneous weighted voting ensemble classifier CV. We choose ten base classifiers as follows: decision tree, multilayer perceptron, logistic regression, SVM, Gaussian processes, passive aggressive classifier, Gaussian naive Bayes, linear classifiers with SGD training, random forest, k-nearest neighbors classifier. All the 24 hyper-parameters (17 continuous, 4 integer and 3 categorical) need to be optimized including voting weights and hyper-parameters in the base classifiers. Our codes are based on scikit-learn [Pedregosa et al., 2011]. We report the generalization performance of CV with default hyperparameters (noted as Default CV) on each dataset as baseline. A tricky method Best C is choosing a base classifier with best 5-fold cross validation error. Best C is employed as the baseline on optimization performance.

We collected 34 UCI classification datasets. Among these, 24 datasets are the source datasets (top 24 data sets in Tabel 2). The rest of them are the target datasets (dataset name in bold in Tabel 2). We organize the experience dataset by running SRACOS on training datasets. For organizing the experience dataset, SRACOS has 200 evaluation budget and repeat for 10 times. The label imbalanced problem exists on this task too. We still use upsampling to balance positive and negative instances. EXPSRACOS is then employed to optimize the hyper-parameters. We set 50 sample budget for all the compared methods.

The results are presented in Table 2. The generalization performance by optimization methods is better than the baseline (Default CV) in most cases. It indicates that hyperparameter optimization can improve generalization performance effectively. EXPSRACOS receives the best optimization and generalization error (the avg. rank is the lowest compared with other methods). EXPSRACOS outperforms SRACOS in most cases. Especially, EXPSRACOS beats SRACOS on 9 target datasets. It indicates the effectiveness of reusing directional model in EXPSRACOS. On the generalization performance, similar results have been obtained. EXPSRACOS outperforms other methods on both source and target datasets, and its performance on the target datasets is significantly better. All these results indicate that the experienced optimization can improve optimization efficiency significantly.

On Neural Network Architecture Optimization

We use two image datasets: MNIST [LeCun et al., 1998] as the source dataset and SVHN [Netzer et al., 2011] as the target dataset. The neural network architecture is illustrated in Figure 2. In each pooling layer, we set pooling type (P t , max or average pooling), kernel size (P k ) and stride size (P s ) as hyper-parameters. In dense layers, the number of each hidden layer is set as hyper-parameters (n1, n2, n3, n4). In CNN 1 or 2, we use two hyper-parameters to dynamically choose the 2nd (C s ,2 ) and 3rd (C s ,3 ) layer, the other hyperparameters (channel size C c , kernel size C k ) are the same among layers. We use Adam as the optimizer, and its learning rate is also an important hyper-parameter. So, there are 19 hyper-parameters in this optimization problem. The generalization performance of a hand-crafted designing net (HCNet) in [Springenberg et al., 2015] is selected as the baseline with the learning rate 0.0002. We separately set optimization epoch size is 20 and 30 for all training in MNIST and SVHN.

We organize the experience dataset by running SRACOS for optimizing on MNIST. The sample budget is set to 200, and optimization process is repeated for 5 times independently. Then, we test Φ on SVHN. The sample budget of all methods is 50. The results of this experiments is presented in Table 3. EXPSRACOS receives the best performance in optimization. Comparing with SRACOS on SVHN, the optimization and generalization error obtained by EXPSRACOS are nearly 0.1% and 1% better than SRACOS. On generalization performance, note that the baseline HC-Net is better than all the non-experienced optimization methods, but EXPSRACOS achieves a significant improvement from the baseline.

5 Conclusions

AutoML tasks such as hyper-parameter optimization and neural network architecture optimization attract attentions incrementally. AutoML tasks are often solved by derivative-free optimization, which, however, commonly suffers from the high evaluation cost. This paper proposes an experienced optimization approach. It utilizes the experience of historical optimization processes to guide the optimization on new tasks. Specifically, the directional model is used to predict the direction of the next samples generated in every algorithm iteration. A pre-sample step is added in the optimization to generate candidate samples and filter them with the directional model. In this way, this framework can eliminate many unnecessary explorations and thus improve the sample effectiveness. Incorporating with a state-of-the-art derivative-free optimization method SRACOS, we implement this framework as EXPSRACOS. We empirically compare EXPSRACOS with other state-of-the-art methods on Ackley function and two autoML tasks. The experiment results show that the experienced optimization with directional model can effectively reduce the sample budget and improve the optimization. Recently Zhou [Zhou, 2016] proposed the new concept of learnware, with properties of reusability, evolvability and comprehensibility. The effort of this paper can be viewed as an effort towards reusability from a new perspective.