EVOLUTIONARY-NEURAL HYBRID AGENTS
Year: 2018

Abstract:
Neural Architecture Search has recently shown potential to automate the design of Neural Networks. The use of Neural Network agents trained with Reinforcement Learning can offer the possibility to learn complex patterns, as well as the ability to explore a vast and compositional search space. On the other hand, evolutionary algorithms offer the greediness and sample efficiency needed for such an application, as each sample requires a considerable amount of resources. We propose a class of Evolutionary-Neural hybrid agents (Evo-NAS), that retain the best qualities of the two approaches. We show that the Evo-NAS agent can outperform both Neural and Evolutionary agents, both on a synthetic task, and on architecture search for a suite of text classification datasets.

text: Neural Architecture Search has recently shown potential to automate the design of Neural Networks. The use of Neural Network agents trained with Reinforcement Learning can offer the possibility to learn complex patterns, as well as the ability to explore a vast and compositional search space. On the other hand, evolutionary algorithms offer the greediness and sample efficiency needed for such an application, as each sample requires a considerable amount of resources. We propose a class of Evolutionary-Neural hybrid agents (Evo-NAS), that retain the best qualities of the two approaches. We show that the Evo-NAS agent can outperform both Neural and Evolutionary agents, both on a synthetic task, and on architecture search for a suite of text classification datasets.

heading: 1 INTRODUCTION
text: Deep Neural Networks (DNN) have yielded success in many supervised learning problems. However, the design of state-of-the-art deep learning algorithms requires many decisions, normally involving human time and expertise. As an alternative, Auto-ML approaches aim to automate manual design with meta-learning agents. Many different approaches have been proposed for architecture optimization, including random search, evolutionary algorithms, Bayesian optimization and DNN trained with Reinforcement Learning.
Deep Reinforcement Learning (deep RL) is one of the most common approaches. It samples architectures from a distribution, which is modeled by a deep neural network. The parameters of the controller model are trained using RL to maximize the performance of the downstream learning algorithm. Architecture search based on deep RL has shown many recent successes in automatic design of state-of-the-art RNN cells (Zoph & Le, 2017), convolutional blocks (Zoph et al., 2017), activation functions (Prajit Ramachandran, 2018), optimizers (Bello et al., 2017; Wichrowska et al., 2017) and data augmentation strategies (Cubuk et al., 2018).
Recently, Real et al. (2018) has shown that evolutionary approaches, with appropriate regularization, can match or surpass the RL-DNN meta learner on architecture search task where sample efficiency is critical. Indeed, those methods can efficiently exploit a single observation of a good trial, when learning based methods require more observations. Classical evolutionary methods have the disadvantage of relying on heuristics or random sampling when choosing mutations to be applied to the parent trial. Unlike approaches based on a Neural Network (NN) controller, they are unable to learn patterns to drive the search.
The scientific contribution of this paper is to introduce a class of Evolutionary-Neural hybrid agents (Evo-NAS). Concretely, we propose an evolutionary agent, where the mutations are guided by a NN trained with RL. This combines both the sample efficiency of Evolutionary agents, and the ability to learn complex patterns, retaining the best of both worlds.
In Section 3 we give a brief description of state-of-the-art Neural and Evolutionary agents, and introduce by comparison the proposed Evo-NAS agent in Section 4. Then, in Section 5, we present and discuss the properties of the proposed Evolutionary-Neural agent, applying it to a synthetic task. Finally, we apply Evo-NAS to architecture search benchmarks, showing that it outperforms both RL-based and Evolution-based algorithms on architecture search for a variety of text classification datasets.

heading: 2 RELATED WORK
text: In recent years, progress has been made in automating the design process required to produce stateof-the-art neural networks. Recent methods have shown that learning-based approaches can achieve state-of-the-art results on ImageNet (Zoph & Le, 2017; Liu et al., 2017). These results have been subsequently scaled by transferring architectural building blocks between datasets (Zoph et al., 2017). Some works explicitly address resource efficiency (Zhong et al., 2018; Pham et al., 2018), which is crucial, as architecture search is known to require vast amount of resources (Zoph & Le, 2017).
Another important approach to architecture search is neuro-evolution (Floreano et al., 2008; Stanley et al., 2009; Real et al., 2017; Conti et al., 2017). Recent work has highlighted the importance of regularizing the evolutionary process, showing that evolution can match or outperform a learningbased baseline (Real et al., 2018). Others have applied genetic algorithms to evolve the weights of the model (Such et al., 2017).
Other than deep RL and evolution, different approaches have been applied to architecture search: cascade-correlation (Fahlman & Lebiere, 1990), boosting (Cortes et al., 2016), deep-learning based tree search (Negrinho & Gordon, 2017), hill-climbing (Elsken et al., 2017) and random search (Bergstra & Bengio, 2012).

heading: 3 BASELINES

heading: 3.1 NEURAL ARCHITECTURE SEARCH
text: Neural Architecture Search (NAS) (Zoph & Le, 2017) uses a RNN controller to perform architectural choices that define a child model. These choices can also include hyperparameters such as learning rate. The resulting child model is then trained on the downstream task, and its accuracy on a validation set is computed. This accuracy serves as the reward for training the RNN controller using a policy gradient approach. In the following sections, we will refer to the standard NAS agent as the Neural agent.

heading: 3.2 REGULARIZED EVOLUTION ARCHITECTURE SEARCH
text: Regularized Evolution (Real et al., 2018) is a variant of the tournament selection method (Goldberg & Deb, 1991). A population of P trained models is improved in iterations. At each iteration, a sample of S models is selected at random. The best model of the sample is mutated to produce a child model with an altered architecture, which is trained and added to the population. The regularization consists of discarding the oldest model of the population instead of the one with the lowest reward. This avoids over-weighting of models that may have reached their high accuracy by chance during the noisy training process. In the following sections, we will refer to the standard Regularized Evolution agent as the Evolutionary agent.

heading: 4 EVOLUTIONARY-NEURAL ARCHITECTURE SEARCH
text: We propose a hybrid agent, which combines an Evolutionary approach with the use of a RL trained Neural controller. The population update and parent sampling is equivalent to Regularized Evolution.
The main difference is in how the mutations are generated. At mutation sampling time, the parent sequence is injected in a standard NAS-RNN controller. The Evolutionary-Neural controller has only one modification, that allows it either to reuse the parent’s action or to sample a new one from the learned distributions over the action space. This decision to keep or re-sample an action is taken independently for any action in the sequence. If an action is re-sampled, it will be conditioned on all the prior actions as in the standard NAS-RNN controller. Concretely, the parent’s action is reused with probability p, and a new action is sampled otherwise, where p is a hyperparameter. This process is summarized in Figure 1.
At training time, the controller parameters are updated in the same way as in the standard NAS-RNN controller.
Note that, compared to Regularized Evolution, this design just affects the distributions from which the mutations are sampled. Regularized Evolution is unable to learn good mutation patterns, since the distributions from which the mutations are sampled are constantly uniform (random sampling). For Evo-NAS, these distributions are initialized as uniform, but with time are updated to promote the patterns of the good models.
Evo-NAS is designed to retain the sample-efficiency of Evolution, which is able to efficiently exploit good trials, while the underlining Neural Network is able to learn biases and complex patterns, as the standard Neural agent.

heading: 4.1 TRAINING
text: We consider two alternative training algorithms:
Reinforce (Williams, 1992). Reinforce is the standard on-policy policy-gradient training algorithm. It is often considered the default choice for applications where a NN needs to be trained to learn a task that has no supervision, but requires to explore a complex space to find the optimal solution, as is in the case of architecture search. This approach has the disadvantage of not being as sample efficient as its off-policy alternatives, which are able to reuse samples. Reinforce is the training algorithm chosen in the original NAS paper (Zoph & Le, 2017).
Priority Queue Training (PQT) (Abolafia et al., 2018). In PQT, samples are generated by sampling from the learned distributions as in Reinforce. However, at training time, the gradients are generated to directly maximize the log likelihood of the best samples produced so far. This training algorithm has the sample efficiency of RL off-policy training approaches, since the best models generate multiple updates. PQT has the simplicity of supervised learning, since the best models are directly promoted as if they constitute the supervised training set, with no need of reward scaling as in Reinforce, or sample probability scaling as in off-policy training.
In the experiment section we will compare these two training approaches and conclude that PQT leads to higher sample-efficiency and better results.

heading: 5 EXPERIMENTS
text: To properly evaluate the advantages and disadvantages of different approaches, we propose to consider two characteristics:
• whether the agent is capable of learning patterns • whether the agent is capable of efficiently exploiting good past experiences
The two characteristics above are independent, and for a fixed architecture search algorithm, both of them may or may not be present. In Table 1, we summarize the characteristics of the methods we aim to compare .

heading: 5.1 LEARN TO COUNT
text: To highlight the properties of the proposed Evo-NAS agent, we evaluated it on a synthetic task. In this task, the agent is asked to choose a sequence a = 〈a1, a2, · · · , an〉 of n integer numbers. Each number is selected from the set [1, n] ∩ Z. Here n is a hyperparameter that controls the difficulty of the task. Given a sequence, a, its imbalance, i(a), is defined as follows:
i(a) = n∑ k=0 (ak+1 − ak)2 (1)
Where we set the initial and last terms a0 = 0 and an+1 = n+ 1. The reward observed by the agent after choosing a sequence a is then:
r(a) = n+ 1
i(a) (2)
Notice that:
• in order to maximize reward, the agent must minimize imbalance. • r(a) ∈ (0, 1]. • there is a single optimal sequence that achieves the reward of 1, namely a = 〈1, 2, · · · , n〉.
The proposed toy task has multiple key properties:
• The size of the search space is nn, which even for small n is already too big for any exhaustive search algorithm to succeed.
• If U is uniform distribution over {1, · · · , n}n then: E a∼U [r(a)] = O
( 1
n2
) .
Moreover, Random Search performs very poorly, as shown by our experiments reported below. This allows to attribute the discovery of good sequences to properties of the algorithm, rather than to accidental discovery over time. • The search space exhibits a sequential structure, with a notion of locally optimal decisions,
making it a good task both for learning patterns, and for mutating past trials by local modifications.
We perform a preliminary tuning of the hyperparameters of the agents to ensure a fair comparison. For the following experiments, we set the decision exploitation probability p = 0.7, the population size P = 500 and the sample size S = 50, for both the Evolutionary and the Evo-NAS agent. We set the learning rate to be 0.0005 for the Neural agent and 0.0001 for the Evo-NAS agent. We set the entropy penalty of 0.1 for the Neural agent and 0.2 for the Evo-NAS agent. PQT maximizes the log likelihood of the top 5% trials for the Neural agent and top 20% trials for the Evo-NAS agent.
We start by comparing Reinforce and PQT as alternative training algorithms for the Neural and EvoNAS agents. The results of the experiments are shown in Figure 2. We found that PQT outperformed Reinforce for both the Neural and the Evo-NAS agent. For the Evo-NAS agent, the gain is especially pronounced at the beginning of the experiment. Thus, we conclude that PQT can provide a stronger training signal than Reinforce. We will use PQT for the following comparison between agents.
The results of the comparison between agents on the “Learn to count” task are shown in Figure 3. We find that PQT provides a stronger training signal, allowing the Neural agent to outperform the Evolutionary agent given enough training. However, the Evolutionary agent is learning faster during the initial 1000 samples, showing higher sample efficiency. Evo-NAS agent initial quick improvement shows its ability to take advantage of the sample efficiency of Evolution. We also observe that learning the proper mutation patterns allows the Evo-NAS agent to find good sequences faster than the Evolutionary agent. Hence, in sample efficiency the Evo-NAS agent strongly outperforms both the Evolutionary and the Neural agent.

heading: 5.2 TEXT CLASSIFICATION TASKS
text: We evaluate the Neural, Evolutionary and Evo-NAS agents on the task of finding architectures for 7 public text classification tasks.
Similarly to (Wong et al., 2018), we design a search space of common architectural and hyperparameter choices that define two-tower feedforward neural networks (FFNN) child models. These architectures are similar to the “wide and deep” models (Cheng et al., 2016). One tower is a deep FFNN, built by stacking: a pre-trained text-embedding module, a stack of fully connected layers, and a softmax classification layer. The deep tower is regularized with L2 loss. The other tower is a wide-shallow layer that directly connects the one-hot token encodings to the softmax classification layer with a linear projection. The wide tower is regularized with L1 loss to promote sparsity. The wide tower allows the model to learn task-specific biases for each token directly, such as trigger words, while the deep tower allows it to learn complex patterns.
The controller defines the child model architecture by selecting a value for every available architectural or hyper-parameter choice. The details of the search space are reported in Table 3. The search space defines the sequence of actions and the values available for each action. The first action selects the pre-trained text-embedding module. The details of the text-embedding modules are reported in Table 4. These modules are available via the TensorFlow Hub service1. Using pretrained textembedding modules has two benefits: first, improves the quality of the child models trained on smaller datasets, and second, decreases convergence time of the child models. Another particularity
1https://www.tensorflow.org/hub
All the experiments in this section are run with a fixed budget: 30 trials are trained in parallel for 2 hours with 2 CPUs. Choosing a small budget allows to run a higher number of replicas for each experiment, to increase the significance of the results. It also makes the budget accessible to most of the scientific community, thus increasing the reproducibility of the results.
During the experiments, the models sampled by the agent are trained on the training set of current text classification task, and the Area under the ROC curve (ROC-AUC) on the validation set is used as the reward for the agent. As the final unbiased evaluation metric, we measure the ROC-AUC computed on the holdout testset, for the child model that achieved the best reward. For the datasets that do not come with a pre-defined train/validation/test split, we split randomly 80/10/10.
We use ROC-AUC as the main metric, since it provides a less noisy reward signal, compared to the more commonly used accuracy. In a preliminary experiment, we validated this hypothesis by running experiments on the ConsumerComplaints task. Then, for a sample of 30 models, we have computed 4 metrics: ROC-AUC on validation and test set, accuracy on validation and test set. The Pearson correlation between the validation ROC-AUC and the test ROC-AUC resulted to be 99.96%, while between the validation accuracy and the test accuracy resulted to be 99.70%. The scatter plot of these two sets is reported in Figure 6.
We validate the results of the comparison between PQT and Reinforce done in Section 5.1 by running 5 experiment replicas for each of the 7 tasks using the Neural controller with both training algorithms. We measure an average relative gain of +1.13% over the final test ROC-AUC achieved by using PQT instead of Reinforce. Thus, we assume that the gains observed by using PQT instead of Reinforce generalize.
We will use PQT for all the following experiments to train the Evo-NAS and Neural agents to maximize the log likelihood of the top 5 trials. For the Evo-NAS and Evolutionary agents, we have set the exploitation probability p to 0.5.
To measure the quality of the models generated by the three agents, we run 10 experiment replicas for each of the 7 tasks, and we measure the test ROC-AUC obtained by the best model generated by each experiment replica. The results are summarized in Table 2 and Figure 4. The Evo-NAS agent
2https://www.tensorflow.org/api_docs/python/tf/contrib/opt/LazyAdamOptimizer
achieves the best performance on all 7 tasks. On 3 out of 7 tasks it significantly outperforms both the Neural and the Evolutionary agents.
We also report the number of trials each of the agents performed during the 2h long experiments, and summarize the results in Table 5 and Figure 7. We find that the Evolutionary and the Evo-NAS agents strongly outperform the Neural agent in terms of number of trials performed. The Evo-NAS agent achieves the largest number of trials on 6 out of 7 datasets, while the Evolutionary agent on 5 out of 7 datasets. On 4 datasets the Evolutionary and Evo-NAS agents perform joint best. We conclude that this shows that the evolutionary algorithms are biased towards faster models, as shown in (Real et al., 2018).
An in depth analysis of the architectures that achieved the best performance is beyond the scope of this paper. However, we want to mention a few relevant patterns, that emerge across tasks. The agent often selects FFNNs with fewer, but wider, layers for the deep part of the network. The learning rate for the best models for both wide and deep parts is in the bottom of the range (0.001). The controller also prefers to disable L1 and L2 regularization. Our interpretation is that reducing the number of parameters is a simpler and more effective regularization, that is preferred over adding L1 and L2 factor to the loss.
To verify that the learning patterns highlighted in Section 5.1 generalize, we plot in Figure 5 the reward moving average for two selected tasks: 20Newsgroups and ConsumerComplaints. For these experiments, we have extended the time budget from 2h to 5h. This time budget extension is needed to be able to capture longer term trends exhibited by the Neural and Evo-NAS agents. We run 3 replicas for each task. In the early stages of the experiments, we notice that the quality of the samples generated by the Neural agent are on the same level as the randomly generated samples, while the quality of the samples generated by the Evo-NAS and Evolutionary agents grows steadily.
In the second half of the analyzed experiments, we notice that the Neural agent starts applying the learnt patterns to the generated samples. The quality of the samples generated by the Evolutionary agent flattens, which we assume is due to the fact that the quality of the samples in the population is close to optimum, and the quality of the samples cannot improve, since good mutations patterns cannot be learned. Finally, we observe that the Evo-NAS agent keeps generating better, samples or even improves.

heading: 6 CONCLUSION
text: We introduce a class of Evo-NAS hybrid agents, which are designed to retain both the sample efficiency of evolutionary approaches, and the ability to learn complex patterns of Neural agents. We experiment on synthetic and text classification tasks, analyze the properties of the proposed Evo-NAS agent, and show that it can outperform both Neural and Evolutionary agents. Additionally, we show that Priority Queue Training outperforms Reinforce also on architecture search applications.

heading: A APPENDIX

Review summaries:
The paper introduces a novel way to do architecture search that uses an RNN to guide the mutation operation. The method and the motivation of the idea as long with the related work are all clearly described. However, the experiments section does not show a big uplift of the method versus the baselines and the number of types of tasks is relatively small (artificial and text). 

The paper proposes a hybrid approach which combines evolution and RL. The key idea is to conduct tournament selection over a population of architectures with learned mutations. The mutations are defined as the output of an RNN controller which either reuses or alters the sequence descriptor of the parent at each step. The proposed hybrid architect is evaluated on both synthetic and text classification tasks and then compared against pure evolutionary and RL-based agents.