Learning Model-Ensemble Policies with Genetic Programming

Schriftenreihe CIplus, Band 3/2015 Herausgeber: T. Bartz-Beielstein, W. Konen, H. Stenzel, B. Naujoks Learning Model-Ensemble Policies with Genetic Programming Oliver Flasch, Martina Friese, Martin Zaefferer, Thomas Bartz-Beielstein, J¨urgen Branke Learning Model-Ensemble Policies with Genetic Programming Oliver Flasch1, Martina Friese1, Martin Zaefferer1, Thomas Bartz-Beielstein1, and J¨urgen Branke2 1Faculty for Computer and Engineering Sciences Cologne University of Applied Sciences, 51643 Gummersbach, Germany [email protected] 2Warwick Business School, University of Warwick Coventry, CV4 7AL, UK [email protected] Abstract. We propose to apply typed Genetic Programming (GP) to the problem of finding surrogate-model ensembles for global optimization on compute-intensive target functions. In a model ensemble, base-models such as linear models, random forest models, or Kriging models, as well as preand post-processing methods, are combined. In theory, an optimal ensemble will join the strengths of its comprising base-models while avoiding their weaknesses, offering higher prediction accuracy and robustness. This study defines a grammar of model ensemble expressions and searches the set for optimal ensembles via GP. We performed an extensive experimental study based on 10 different objective functions and 2 sets of base-models. We arrive at promising results, as on unseen test data, our ensembles perform not significantly worse than the best base-model. Keywords: Ensemble Methods, Genetic Programming, Surrogate-Model-Based Optimization 1 Introduction The application of surrogate-model based methods for the purpose of solving cost extensive and time consuming optimization problems is an established technique. Surrogate models, as employed in methods like Efficient Global Optimization (EGO) [19] or Sequential Parameter Optimization (SPO) [1] offer several advantages. While their main goal is often to reduce the number of costly target function evaluations, one can also benefit from the information surrogate models provide on the problem. This can include information on the shape of the optimized landscape, interactions between parameters or their individual importance. A question that often arises with such approaches is the choice of the modeling technique (e.g., tree-based, Support Vector Machines or Kriging). This paper 2 Friese et al. will use ”base-models” to refer to such different model types. Depending on the task at hand, a certain individual base-model might be most promising. In many cases however it may be unclear which of several candidates is best suited. For instance, one base-model might provide better global approximation than another, while another base-model can handle discontinuous regions of the design space with more ease. Thus it is of interest to develop methods with which to choose from or combine substantially different base-models. Relevant cross references to similar problems as well as previous studies on this issue are reviewed in Sec. 2. In this very first step towards learning a meaningful ensemble policy, a Genetic Programming (GP) system is used to combine the different models with very simple operators. The methods to this end are introduced in Sec. 3. We limit ourselves to the modeling stage, due to the complexity of the problem. Employing generated ensemble policies in an actual optimization framework will remain for a detailed investigation in following publications. Thus, our approach is tested for its success in modeling simple numerical test functions. The problem setup, including test functions and employed modeling techniques, are described in Sec. 4. Experiment results are given in Sec. 5 and analyzed in Sec. 6. This text closes with a summary and outlook in Sec. 7. 2 Previous Research Ensembles are not a new topic, neither in modeling nor in surrogate model supported optimization. As the costly optimization problems at hand warrant only very sparse sampling of data, some classical ensemble approaches like bootstrap aggregating (bagging) [2] or boosting [20, 28] are not well applicable. Also, bagging is often, although not always [22, 6], employed to build ensembles of homogeneous basemodels, i.e. models of the same type (e.g., only tree or only linear). In a similar way boosting has been used to combine homogeneous base-models to a stronger set of models, for instance as applied in evolutionary optimization by Holeˇna et al. [17]. With a different concept, Ong et al. [27] combined homogeneous base-models by building them locally around individuals of an evolutionary algorithm’s population, thus building different models in different regions of the design space. Another approach to splitting the design space is that of Gramacy et al. [15]. There, trees that split the design space are learned, applying Gaussian process or linear models in the various divisions. Two different ensemble policies have been tested by Lim et al. [26] for the purpose of enhancing a Surrogate Assisted Memetic Algorithm. They combined base-models either by aggregation or by selecting the best solution from each model for evaluation on the real target function. Focusing on a heterogeneous set of base-models, Gorissen et al. [14] combine models using a genetic algorithm. In their implementation, ensembles occur when Learning Model-Ensemble Policies with Genetic Programming 3 two model types are selected for recombination. The ensembles created are simply an averaged combination of the models. Several alternative approaches were recently investigated by Friese et al. [12]. They grouped approaches into two categories, single-evaluation and multipleevaluation. Single-evaluation approaches view the problem of choosing a model from the ensemble as a multi armed bandit problem [13]. That means, only information from one model is chosen in each sequential optimization step. Multipleevaluation approaches train every model in each step, thus using information from all of them. The single-evaluation approach is also taken by Hess et al. [16], who introduce their algorithm termed PROGRESS. PROGRESS is an enhanced algorithm for solving multi armed bandit problems, specifically adapted to the problem of selecting a surrogate model for optimization. There are further approaches, including some not solely intended for being employed in surrogate model optimization. One example is the approach of Frayman et al. [10]. Frayman [10] et. al use a neural network (Multi Layer Perceptron MLP) to train an ensemble combining linear, MLP, logistic regression and k-nearest neighbor models. This approach can be classified as a variation of stacked generalization, or model stacking [29, 3]. 3 Methods This section describes the various methods used in this work, including model ensembles and model combination policies. It is shown how model combination policies are evaluated and how they are evolved by GP. 3.1 Model Ensembles It still remains unclear how an ideal policy would combine information from fundamentally different base-models in a meaningful way. While theoretical considerations or ideas from other fields (i.e. multi armed bandit problems) do yield Ensemble-Policies that work to some extend, we would like to suggest a way to learn such policies in a less constricted environment. The idea presented here attempts to do so with a GP approach. That is, the different models are viewed as parameters in a symbolic regression problem. With the terms of Friese et al. we will herein attempt to learn a policy for a multiple-evaluation approach [12] Multiple-evaluation approaches train every model in each step, combining or selecting from the information yielded. As single evaluation approaches need several optimization steps to learn the right behavior, they may often be infeasible for the costly problems of concern in surrogate model based optimization. In this paper we call the set of available base-models M. A specific basemodel will be referred to as mi, where i represents the index of the model type (e.g., 1 is a linear model, 2 is a Kriging model, etc.). During experiments, each 4 Friese et al. miwill be trained on a fixed training data set and yield a vector of responses yi for a second, independent validation data set. A policy combining several miwill be referred to as πk. Here, krepresents a counter, as several policies can be learned, for instance by restarting a GP run with a different seed. In the following, the models mi, as well as policies πkare described as realvalued functions defined in d-dimensional bounded parameter space D⊂Rd. The dimensionality d, as well as the bounds, or region of interest, of Dare dependent on the objective function. xdtxd<txd≥t mean LM x mean * RF x 1.88 decision x2−0.59 −1.75 0.03 Fig. 1. Example of a GP-generated policy shown as an expression tree. Fig. 1 shows the expression tree of the following GP-evolved example policy: mean[LM(x),mean[RF(x)×1.88,decision(x,2,−0.59,−1.75,0.03)]] This policy combines a linear model (LM) with a random forest model (RF) by calculating the arithmetic mean of the model outputs. The RF output is further post-processed by scaling and mixing (also via arithmetic mean) with the output of a simple GP-evolved decision tree. As we are only using 2D test functions in this study, base-models and model ensembles can be visualized as surface plots. Learning Model-Ensemble Policies with Genetic Programming 5 In these plots, the first dimension of the bounded parameter space Dis assigned to the X (width) axis, the second dimension of Dto the Y (depth) axis and the model output to the Z (height) axis. As an example, we applied the ensemble policy of Fig. 1 to the 2D Weierstrass function with the bounds (domain) shown in Tab. 1. Fig. 2 provides a surface plot of this test function. As our example policy refers to the LM and RF basemodels, both models have to be fitted to training data. Surface plots of these base-model fits are shown in Fig. 3 and Fig. 4, respectively. Based on these fits, the output of our example policy is shown as a surface plot in Fig. 5. Fig. 2. Surface plot of the 2D Weierstrass test function. 6 Friese et al. Fig. 3. Surface plot of a linear model (LM) fit of the 2D Weierstrass test function. Learning Model-Ensemble Policies with Genetic Programming 7 Fig. 4. Surface plot of a random forest (RF) model fit of the 2D Weierstrass test function. 8 Friese et al. Fig. 5. Surface plot of an ensemble fit of the 2D Weierstrass test function based on the policy shown in Fig. 1. The base-model fits used in the ensemble are shown in Fig. 3 and Fig. 4. Learning Model-Ensemble Policies with Genetic Programming 15 set: small set: full ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●● ●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ●● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ●● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ●●● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ●●● ● ● ● ● ●● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ●● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ●●● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ●● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●●●● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 1 1 10 10 0.1 1 1e−05 1e−01 1e+03 1e+07 10 1 10 100 1000 10000 1e−12 1e−08 1e−04 1e+00 f: weierstrass f: griewangk f: branin f: mex_hat f: ackley f: discus f: rastrigin f: kotanchek f: rosenbrock f: sphere MARS RF LM EnsVal EnsTst MARS RF LM EnsVal EnsTst SVM KF MLP base models and model ensembles SRMSE Fig. 7. Boxplot of experimental results. EnsVal are the model ensembles on validation data, i.e. their fitness as seen by the GP system. EnsTst are the model ensembles on validation data. Each box is based on 48 ∗47 = 2256 values. Only the EnsVal boxes are based on just 48 values, which are the fitness values as seen by the GP system. 16 Friese et al. a single exception) perform no better than each best base-model on test data. While the base-models mostly avoid over-fitting, the too well adapted structure of a policy can reintroduce that problem. Enabling the complexity criterion, or cross validating the fitness values might be possible ways to deal with that issue. However, since complexity is already limited due to the tree depth limit it would be more promising to look at better validation of fitness values. Still, even if over-fitting is avoided appropriately, it might occur that ensembles will be unable to outperform the best base-model. The results on Discus and Sphere function are good examples for that. There, it is unlikely that the LM base-model can be outperformed by a heterogeneous ensemble policy. 7 Summary and Outlook For the purpose of optimizing costly global optimization problems, it is of interest how to combine a set of heterogeneous base-models, which are then exploited in a surrogate model optimization framework. The goal of this paper was to make a first step towards learning ensemble policies for surrogate based optimization, using genetic programing. That first step consisted in testing the necessary methods to build such an ensemble policy. The error in approximating numerical test functions was used as a quality indicator. The necessary grammar of model ensemble expressions was defined, and it was shown that the suggested framework is working. However, our approach only produced a significant improvement in one of twenty cases. The main problem, which occurs regardless of the limited complexities (i.e. the tree depth limit), was over-fitting. It can also be noticed that several of the employed numerical test functions are best solved with a strategy that simply selects from the base models instead of learning any more complex policies. Therefore, we plan to first improve the approach, in an attempt to avoid the occurring over fitting. Since complexity is already somewhat limited, we would suggest to cross validate fitness values of each ensemble policy during the GP run. It is also of interest to extend the process suggested here. That includes improving the used set of GP operators, as well as to consider using further information provided by the base models. For instance, Kriging yields an error estimate. Integrating such an error estimate reasonably would be beneficial, as it is often successfully used in surrogate model based optimization to balance exploration and exploitation. In connection with this, a process of identifying features of the optimized landscape could be incorporated. This would allow to actually learn policies which are able to work on more than just one target function. Besides, due to the limitations of the employed test functions, using real world problems would be significantly more interesting. Not only would they indicate behavior more relevant for practical applications. Real world problems might also yield landscapes which are more interesting to be approximated by an ensemble. Learning Model-Ensemble Policies with Genetic Programming 17 In addition, the error measure employed should be further investigated. It is not clear whether it is the best choice when surrogate model optimization is the application. Alternatively, some kind of permutation error might be more suited. In the long run of course the model policies found should be tested for their actual purpose, which is surrogate model optimization. Therefore, a second step could involve testing such policies as surrogates in an optimization framework like SPO. Or else, the actual optimization performance itself could be used as a fitness measure in the GP system. That, however, would raise the computational effort considerably. Finally, we consider to test this approach for a rather different application, which is ensembles of time series prediction algorithms. Acknowledgments This work has been kindly supported by the Federal Ministry of Education and Research (BMBF) under the grants MCIOP (FKZ 17N0311) and CIMO (FKZ 17002X11). References 1. T. Bartz-Beielstein, K. E. Parsopoulos, and M. N. Vrahatis. Design and analysis of optimization algorithms using computational statistics. Applied Numerical Analysis and Computational Mathematics (ANACM), 1(2):413–433, 2004. 2. L. Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996. 3. L. Breiman. Stacked regressions. Machine Learning, 24:49–64, 1996. 4. L. Breiman. Random forests. Machine Learning, 45(1):5 –32, 2001. 5. C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1–27:27, 2011. 6. A. L. V. Coelho and D. S. C. Nascimento. Letters: On the evolutionary design of heterogeneous bagging models. Neurocomput., 73(16-18):3319–3322, Oct. 2010. 7. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast elitist multi-objective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation, 6:182– 197, 2000. 8. O. Flasch, O. Mersmann, and T. Bartz-Beielstein. RGP: An open source genetic programming system for the R environment. In M. Pelikan and J. Branke, editors, Genetic and Evolutionary Computation Conference, GECCO 2010, Proceedings, Portland, Oregon, pages 2071–2072. ACM, 2010. 9. A. Forrester, A. Sobester, and A. Keane. Engineering Design via Surrogate Modelling. Wiley, 2008. 10. Y. Frayman, B. F. Rolfe, and G. I. Webb. Solving regression problems using competitive ensemble models. In Proceedings of the 15th Australian Joint Conference on Artificial Intelligence: Advances in Artificial Intelligence, AI ’02, pages 511–522, London, UK, UK, 2002. Springer-Verlag. 11. J. H. Friedman. Multivariate adaptive regression splines. Ann. Stat., 19(1):1–141, 1991. 12. M. Friese, M. Zaefferer, T. Bartz-Beielstein, O. Flasch, P. Koch, W. Konen, and B. Naujoks. Ensemble based optimization and tuning algorithms. In F. Hoffmann and E. H¨ullermeier, editors, Proceedings 21. Workshop Computational Intelligence, pages 119–134. Universit¨atsverlag Karlsruhe, 2011. 18 Friese et al. 13. J. Gittins. Bandit processes and dynamic allocation indices. J. R. Statist. Soc. B, 41:148–164, 1979. 14. D. Gorissen, T. Dhaene, and F. D. Turck. Evolutionary model type selection for global surrogate modeling. J. Mach. Learn. Res., 10:2039–2078, Dec. 2009. 15. R. B. Gramacy and H. K. H. Lee. Bayesian treed Gaussian process models. Technical report, Dept. of Applied Math & Statistics, University of California, Santa Cruz, 2006. 16. S. Hess, T. Wagner, and B. Bischl. Progress: Progressive reinforcement-learningbased surrogate selection. In Proceedings of Seventh Learning and Intelligent OptimizatioN Conference LION 2013, 2013. 17. M. Holeˇna, D. Linke, and N. Steinfeldt. Boosted neural networks in evolutionary computation. In Proceedings of the 16th International Conference on Neural Information Processing: Part II, ICONIP ’09, pages 131–140, Berlin, Heidelberg, 2009. Springer-Verlag. 18. Information technology – Syntactic metalanguage – Extended BNF, 1996. 19. D. Jones, M. Schonlau, and W. Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13:455–492, 1998. 20. M. Kearns. Thoughts on hypothesis boosting. Unpublished manuscript, 1988. 21. M. Keijzer. Scaled symbolic regression. Genetic Programming and Evolvable Machines, 5(3):259–269, sep 2004. 22. S. Kotsiantis, D. Kanellopoulos, and I. Zaharakis. Bagged averaging of regression models. In I. Maglogiannis, K. Karpouzis, and M. Bramer, editors, Artificial Intelligence Applications and Innovations, volume 204 of IFIP International Federation for Information Processing, pages 53–60. Springer US, 2006. 23. J. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge MA, 1992. 24. B. Lang. Monotonic multi-layer perceptron networks as universal approximators. In W. Duch, J. Kacprzyk, E. Oja, and S. Zadrozny, editors, Artificial Neural Networks: Formal Models and Their Applications ? ICANN 2005, volume 3697 of Lecture Notes in Computer Science, pages 31–37. Springer Berlin Heidelberg, 2005. 25. R. V. Lenth. Response-surface methods in R using rsm (updated to version 1.40). Technical report, The University of Iowa, 2010. 26. D. Lim, Y. soon Ong, B. Sendhoff, and Y. Jin. A study on metamodeling techniques, ensembles, and multi-surrogates in evolutionary computation. In In The 9th Annual Conference on Genetic and Evolutionary Computation (GECCO-2007, pages 1288–1295. ACM Press, 2007. 27. Y. S. Ong, P. B. Nair, and A. J. Keane. Evolutionary optimization of computationally expensive problems via surrogate modeling. AIAA Journal, 41(4):687–696, 2003. 28. R. E. Schapire. A brief introduction to boosting. In Proceedings of the 16th international joint conference on Artificial intelligence - Volume 2, IJCAI’99, pages 1401–1406, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. 29. D. H. Wolpert. Stacked generalization. Neural Networks, 5:241–259, 1992. Kontakt/Impressum Diese Ver¨offentlichungen erscheinen im Rahmen der Schriftenreihe ”CIplus”. Alle Ver¨offentlichungen dieser Reihe k¨onnen unter www.ciplus-research.de oder unter http://opus.bsz-bw.de/fhk/index.php?la=de abgerufen werden. K¨oln, Januar 2012 Herausgeber / Editorship Prof. Dr. Thomas Bartz-Beielstein, Prof. Dr. Wolfgang Konen, Prof. Dr. Boris Naujoks, Prof. Dr. Horst Stenzel Institute of Computer Science, Faculty of Computer Science and Engineering Science, Cologne University of Applied Sciences, Steinm¨ullerallee 1, 51643 Gummersbach url: www.ciplus-research.de Schriftleitung und Ansprechpartner/ Contact editors office Prof. Dr. Thomas Bartz-Beielstein, Institute of Computer Science, Faculty of Computer Science and Engineering Science, Cologne University of Applied Sciences, Steinm¨ullerallee 1, 51643 Gummersbach phone: +49 2261 8196 6391 url: http://www.gm.fh-koeln.de/~bartz/ eMail: [email protected] ISSN (online) 2194-2870