We propose Efficient Neural Architecture Search (ENAS), a faster and less expensive approach to automated model design than previous methods. In ENAS, a controller learns to discover neural network architectures by searching for an optimal path within a larger model. The controller is trained with policy gradient to select a path that maximizes the expected reward on the validation set. Meanwhile the model corresponding to the selected path is trained to minimize the cross entropy loss. On the Penn Treebank dataset, ENAS can discover a novel architecture thats achieves a test perplexity of 57.8, which is state-of-the-art among automatic model design methods on Penn Treebank. On the CIFAR-10 dataset, ENAS can design novel architectures that achieve a test error of 2.89%, close to the 2.65% achieved by standard NAS . Most importantly, our experiments show that ENAS is more than 10x faster and 100x less resource-demanding than NAS. Neural architecture search (NAS) has been applied successfully to design model architectures for image classification and language modeling BID0 BID3 BID6. NAS however is computationally expensive and time consuming: for example, use 450 GPUs and train for 3-4 days. Meanwhile, using less resources tends to produce less compelling BID31 BID0.The main computational bottleneck of NAS is the training of each child model to convergence to measure its accuracy. We believe that it is very inefficient and wasteful to train every child model and then throw away all the trained weights even though the child models have much in common. The graph represents the entire search space while the red arrows define a model in the search space, which is decided by a controller. Here we assume that node 1 is the input to the model whereas nodes 3, 5, and 6 are the outputs of the model. The goal of this work is to remove this inefficiency by enabling more sharing between the child models. This idea is similar to the concept of weight inheritance in neuro-evolution (e.g., BID33). To understand our method, we first need to understand the standard NAS. In standard NAS BID0, an RNN controller is trained by policy gradient to search for a good architecture, which is basically a computational graph. Our observation is that all of the graphs, that NAS has iterated over, can be viewed as sub-graphs of a larger graph. In other words, we can represent the space of these graphs as a single directed acyclic graph (DAG). As illustrated in FIG0, a neural network architecture can be found by taking a subset of edges in this DAG. This design is advantageous because it enables sharing parameters among all architectures in the search space. There is growing interest in improving the efficiency of neural architecture search. Concurrent to our work are the promising ideas of using learning curve prediction to skip bad models BID1, predicting the accuracies of models before training BID7, using iterative search method for architectures of growing complexity BID25 ), or using hierarchical representation of architectures BID26. Our method is also inspired by the concept of weight inheritance in neuroevolution, which has been demonstrated to have positive effects at scale BID33.Closely related to our method are other recent approaches that avoid training each architecture from scratch, such as convolutional neural fabrics -ConvFabrics BID34 and SMASH BID5. These methods are more computationally efficient than standard NAS. However, the search space of ConvFabrics is not flexible enough to include novel architectures, e.g. architectures with arbitrary skip connections as in. Meanwhile, SMASH can design interesting architectures but requires a hypernetwork to generate the weights, conditional on the architectures. While a hypernetwork can efficiently rank different architectures, as shown in the paper, the real performance of each network is different from its performance with parameters generated by a hypernetwork. Such discrepancy in SMASH can cause misleading signals for reinforcement learning. Even more closely related to our method is PathNet BID10, which uses evolution to search for a path inside a large model for transfer learning between Atari games. In the following, we will first present our search space to design recurrent cells for recurrent networks. We will then explain how to train, and infer with the controller. Finally, we will explain our search space to design convolutional architectures. To facilitate our discussion of ENAS, we first describe how we employ ENAS to design a recurrent cell. The search space of ENAS is a Directed Acyclic Graph as mentioned in Section 1. The DAG has N nodes where the edges represent the flow of information between these N nodes. Similar to NAS, ENAS has a controller RNN, which decides which edges are activated and which computations are performed at each node. To create a recurrent cell, the controller RNN samples N blocks of decisions. Here we illustrate the ENAS mechanism via a simple example for a recurrent cell with N = 4 computational nodes. Let x t be the input signal for a recurrent cell (e.g., word embedding), and h t−1 be the output from the previous time step. The example cell, which we visualize in FIG1, is sampled as follows.1. At node 1: The controller first samples an activation function. In our example in FIG1, it chooses the tanh activation function, which means that node 1 of the recurrent cell should compute DISPLAYFORM0 ). 2. At node 2: The controller then samples a previous index and an activation function. In our example, it chooses the previous index 1 and the activation function ReLU. Thus, node 2 of the recurrent cell should compute h 2 = ReLU(h 1 · W2,1). 3. At node 3: The controller again samples a previous index and an activation function. In our example, it chooses the previous index 2 and the activation function ReLU. Therefore, h 3 = ReLU(h 2 · W (h) 3,2 ). 4. At node 4: The controller again samples a previous index and an activation function. In our example, it chooses the previous index 1 and the activation function tanh, leading to h 4 = tanh (h 1 · W4,1). 5. For the output, we simply average all the loose ends, which are the nodes that are not input to any other nodes. In our example, since the indices 3 and 4 were never sampled to be the input for any node, the recurrent cell uses their average (h 3 + h 4)/2 as its output. In the example above, we note that for each pair of nodes j <, there is an independent parameter matrix W (h),j. As shown in the example, the controller decides which parameter matrices are used, by choosing the previous indices. Therefore, in ENAS, all recurrent cells in a search space share the same set of parameters. Our search space includes an exponential number of configurations. Specifically, if the recurrent cell has N nodes and we allow 4 activation functions (namely tanh, ReLU, identity, and sigmoid), then the search space has 4 N ×N! configurations. In our experiments, N = 12, which means there are approximately 10 15 models in our search space. Our controller network is a two-layer LSTM BID16 which samples decisions via softmax classifiers. The controller network samples these decisions in an autoregressive fashion: the decision in the previous step is fed as input embedding into the next step. At the first step, the controller network receives an empty embedding as input. In ENAS, there are two sets of learnable parameters: the parameters of the controller LSTM, denoted by θ, and the shared parameters of the child models, denoted by ω. The training procedure of ENAS consists of two alternating phases. The first phase trains ω, the shared parameters of the child models, on a whole pass through the training data set, and the second phase trains θ, the parameters of the controller LSTM, for a fixed number of steps. These two phases are alternated during the training of ENAS. In our experiments with the Penn Treebank dataset, for each phase of training ω, we train ω for 450 steps with SGD, each on a batch of 64 examples, where gradients are computed using back-propagation through time, truncated to 35 time steps. Meanwhile, for each phase of training θ, we train it for 2000 steps with the Adam optimizer and REINFORCE. More details of their training are as follows. Training the shared parameters ω of the child models. In this step, we fix the policy π(m; θ) and perform stochastic gradient descent (SGD) updates on ω to minimize the expected loss function DISPLAYFORM0 Here, L(m; ω) is the standard cross-entropy loss, computed on a minibatch of training data, with a model m sampled from π(m; θ). The gradient is computed via the Monte Carlo estimate DISPLAYFORM1 Note that Eqn 1 provides an unbiased estimate of the gradient DISPLAYFORM2 Therefore, according to Chapter 3.3.2 of BID4, with an appropriate learning schedule, the SGD updates of ω converge almost surely. While convergence is guaranteed, these updates on ω have an inherently larger variance than SGD performed on a fixed model m. Nevertheless, we find that M = 1 works just fine, i.e. we can update ω using the gradient from any single model m sampled from π(m; θ). As mentioned, we train ω for a whole pass through the training data set. Training the parameters of θ of the controller LSTM. In this step, we fix ω and update the policy parameters θ, aiming to maximize the expected reward DISPLAYFORM3 We employ the Adam optimizer BID20, for which the gradient is computed using REINFORCE BID37, with a moving average baseline to reduce variance. We compute the reward R(m, ω) on the validation set, rather than the training set to encourage ENAS, to select the model that generalizes well rather than the model that overfits the training set well. In our experiments with language modeling, the reward function is c/valid ppl, where the perplexity is computed on a minibatch, also sampled from the validation set. Later, in our experiments with image classification, the reward function is the classification accuracy on a minibatch of images sampled from the validation set. Inference. We discuss how to derive novel architectures from a trained ENAS model. Following, we sample several models from the trained policy π (m, θ). For each sampled model, we compute its reward on a single minibatch sampled from the validation set. We then take the model with the highest reward to re-train from scratch. We now discuss the search space for convolutional architectures. Recall that in the search space of the recurrent cell, the controller RNN samples two decisions at each decision block: 1) what previous node to connect to and 2) what activation function to use. In the search space for convolutional models, the controller RNN also samples two sets of decisions at each decision block: 1) what previous node to connect to and 2) what computation operation to use. The decision of what previous node to connect to allows the model to form skip connections BID15; whereas the decision of what computation operation to use sets a particular layer into convolution or average pooling or max pooing. These decisions help construct a layer in the convolutional model. To be even more flexible, instead of deciding if a particular layer is convolution or average pooling or max pooling, we change the search space to blend all these choices together. To achieve this, we treat all operations such as convolution, average pooling, and max pooling as channels, and allow the controller to select a mask over these channels. For example, in our experiments, we allow the controller to choose a mask over how many conv1x1, conv3x3, conv5x5, conv7x7, average pooling, max pooling operations to use (see FIG2 . Each operation at each layer in our network has its own convolutional parameters. During each data pass, only the parameters corresponding to the active channels are used and updated. The network of N layers, where each layer has 6 channels as described. Bottom: A block of the controller network, which consists of 6 binary masks, followed by the steps that sample skip connections. For the skip connections, at layer k, up to k − 1 mutually distinct previous indices are sampled. For example, at layer k = 5, let's suppose the controller samples {2, 4}, then the outputs of layer 2 and layer 4 will be concatenated and sent to layer 5 via skip connections. In our experiments with the CIFAR-10 dataset, the training of the controller LSTM and the child models are also alternating. For each phase of training θ, we train it for 2000 steps with the Adam optimizer and REINFORCE. Meanwhile, for each phase of training the shared parameter ω, we train it for 450 minibatches, each has 100 images, using Nesterov Momentum BID32. An alternative to designing the entire convolutional network is to design smaller modules and then fit repeats of them together BID40. FIG3 illustrates this approach, where the convolutional cell and reduction cell architectures are to be designed. We now discuss how to use ENAS to search for the architecture of these cells. Following, we sample both our convolutional cell and our reduction cell using an RNN controller. Specifically, at each decision block, the controller RNN samples for two sets of decisions: 1) two previous nodes to be used as inputs to the current block and 2) two operations to respectively apply to the two sampled nodes. We allow the following 5 operations: identity, separable convolution with kernel size 3x3 and 5x5, and average pooling and max pooling with kernel size 3x3. Note that each cell receives two input nodes, indexed by node 1 and node 2, corresponding to the outputs of the two previous cells in the entire network. FIG4 depicts an example run of our controller in the search space with 4 nodes. As with our other search spaces, each operation in each cell has its own parameters. During each data pass, only the relevant parameters are used and trained with their corresponding gradients. In the following, we will show our experimental with ENAS to design recurrent cells on the Penn Treebank dataset and to design convolutional architectures on the CIFAR-10 dataset. We then present an ablation study which shows the role of ENAS in discovering novel architectures, as well as details regarding the efficiency of ENAS. Dataset. We first apply ENAS to the task of language modeling, whose goal is predict next words in a text given a history of previous words, by fitting a probabilistic model over sentences. We use the Penn Treebank dataset (PTB) BID28, a well-studied language modeling benchmark. In this experiment, we show that ENAS discovers a novel recurrent cell which, without extensive hyper-parameters tuning, can outperform models with the same or more parameters. Training details. Our controller is trained using Adam , with a learning rate of 0.001. We use a tanh constant of 2.5 and a temperature of 5.0 for the sampling logits BID2. We also add the controller's sample entropy to the reward, with a weight of 10 −4. Additionally, we augment the simple transformations between the constructed recurrent cell's nodes with highway connections BID41. For instance, instead of having h 2 = ReLU(h 1 · W (h) 2,1 ) as shown in the example from Section 3.1, we have DISPLAYFORM0 2,1 ). More details can be found in Appendix A. A novel RNN cell found in our search space is shown in FIG5.The shared parameters of the child models ω are trained using SGD with a learning rate of 0.2, decayed by a factor of 0.9 after every 3 epochs starting at epoch 15, for a total of 150 epochs. During the architecture search process, following BID29, we randomly reset the starting state with probability of 0.001. We also tie the model's word embeddings matrix with its softmax matrix BID18. When retraining the architecture recommended by the controller, however, we use variational dropout BID11, an 2 regularization with weight decay of 10 −7, and a state slowness regularization of 0.0005 BID30.Results. Running on a single Nvidia GTX 1080Ti GPU, ENAS finds the recurrent cell in less than 10 hours. This cell is depicted in FIG5. Table 1 presents our in comparison with other methods. The ENAS cell, with 24M parameters, outperforms the NAS cell and has a similar performance to the LSTM model that uses extensive hyperparameters tuning BID29 ), which we did not do. Our ENAS cell has a few interesting properties. First, all non-linearities in the cell are either ReLU or tanh, even though the search space also has two other functions: identity and sigmoid. We suspect this cell is a local optimum, similar to the observations by. When we randomly pick some nodes and switch the non-linearity into identity or sigmoid, the perplexity increases up to 8 points. When we randomly, swith some ReLU nodes into tanh or vice versa, the perplexity also increases, but only up to 3 points. Dataset. The CIFAR-10 dataset BID22 ) consists of 50,000 training images and 10,000 test images. We use the standard data pre-processing and augmentation techniques, i.e., subtracting the mean and dividing the standard deviation from each channel computed on the training images, centrally padding the training images to 40 × 40 and randomly cropping them back to 32 × 32, and randomly flipping them horizontally. Search spaces. In Section 3.3, we present a search space for convolutional architectures in which the controller can make decisions over skip connections and the mask over the channels. To improve our , we additionally explore two restricted versions of this search space: one where the controller only needs to make decisions of the mask over the channels and one where the controller only needs to make decisions of the skip connections. More details are available in Appendix B.1. Searching for the masks over channels. We fix a pattern of skip connections and search for the masks at each branch and each layer in a 12-layer network. The pattern that we use is the dense pattern BID17. 2. Searching for skip connections. We force all the convolutions to have the filter size of 3 × 3, and only search for the skip connections.3. Searching for convolutional and reduction cells. We search for both cells as discussed in Section 3.4.Training details. The shared parameters ω are trained with Nesterov momentum , where the learning rate follows the cosine schedule with l max = 0.05, l min = 0.001, T 0 = 10 and T mul = 2 BID27. Each architecture search is run for 10 + 20 + 40 + 80 + 160 = 310 epochs. The parameter ω is initialized from a scaled Gaussian as described in BID14. We also apply an 2 weight decay of 10 −4. The same settings are employed to train the architectures recommended by the controller. The policy parameters θ are initialized uniformly in [−0.1, 0.1], and trained with the Adam optimizer at a learning rate of 10 −3. We additionally utilize three techniques to prevent the premature convergence of REINFORCE. First, we apply a temperature τ = 5.0 and a tanh constant c = 2.5 to the controller's logits. Second, we add to the reward the entropy term of the controller's samples weighted by λ ent = 0.1, which discourages convergence BID38. Lastly, we enforce the sparsity in the skip connections by adding to the reward the Kullback-Leibler divergence between: 1) the skip connection probability between any two layers and 2) our chosen probability ρ = 0.4, which represents the prior belief of a skip connection being formed. The KL divergence term is weighted by λ kl = 0.5.Tricks to stabilize and improve training. We find the following tricks crucial for achieving good performance with ENAS.• Structure of Convolutional Layers. Each convolutional operation in our method is followed by a batch normalization BID19 and then a ReLU layer. We find the alternate setting of batch norm-conv-ReLU to have worse .• Stabilizing Stochastic Skip Connections. If a layer receives skip connections from multiple layers before it, then these layers' outputs are concatenated in their depth dimension, and then a convolution of filter size 1 × 1 (followed by a batch normalization layer and a ReLU layer) is performed to ensure the number of output channels is still equal to C.• Global Average Pooling. After the final convolutional layer, we average all the activations of each channel and then pass them to the Softmax layer. This trick was introduced by BID24, with the purpose of reducing the number of parameters in the dense connection to the Softmax layer to avoid overfitting. The last two tricks are extremely important, since the gradient updates of the shared parameters ω, as described in Eqn 1, have a very high variance. In fact, we find that without these last two tricks, the training of ENAS is very unstable. Results. Table 2 summarizes the test errors of ENAS and other approaches. As can be seen from the table, ENAS successfully found several architectures that outperform other automatic model designing approaches with the same usage of computing resource. In particular, in the general search space, ENAS takes 15.6 hours to find a model that achieves 4.23% error rate on CIFAR-10. This model outperforms all but one model reported by, while taking 30x less time and using 800x less computing resource to discover. In the restricted search space over the masks, ENAS takes 11.6 hours to find a model that achieves the test error of 4.35%. The ing model, depicted in FIG6 -Top Left, almost always has 64 or 96 channels at each branch and each layer, indicating that the controller does not choose to activate all blocks. This is the desired behavior, as activating all channels would over-parametrize the model and in overfitting. Moreover, the fact that the model found in a restricted search space has similar performance to the model found in the general search space indicates that ENAS can discover skip connection patterns that are comparable to the dense pattern, which is the state-of-the-art human-designed architecture on CIFAR-10 BID17.In the restricted search space over skip connections, ENAS takes 12.4 hours to discover the pattern of skip connections depicted in FIG6 BID34 16 21.2 7.43 Macro NAS with Q-Learning BID0 11 11.2 6.92 Net Transformation BID6 17 19.7 5.70 FractalNet BID23 21 38.6 4.60 SMASH BID5 211 16.0 4.03 NAS 39 7.1 4.47 NAS + more filters Table 2: Classification error rates of ENAS and other methods on CIFAR-10. In this table, the first block presents the state-of-the-art models, all of which are designed by human experts. The second block presents various approaches that design the entire network. ENAS outperforms all these methods but NAS, which requires much more computing resource and time. The last block presents techniques that design modular cells which are used to build a large model. ENAS outperforms MicroNAS, which uses 32 GPUs to search, and achieves similar performance with NASNet-A.that skip connections are formed much more densely at higher layers than at lower layers, where most connections are only between consecutive layers. The model has the test error of 5.04%, which is slightly worse than the one found in the restricted search space over masks. However, if we increase the number of output channels from 256 to 512, then the network achieves the test error of 3.87%.In the search space over cells, ENAS takes 11.5 hours to discover the convolution cell and the reduction cell, which are shown in FIG6 -Bottom. With the convolutional cell replicated for 6 times, ENAS achieves 3.54% test error, which is on par with the 3.41% error of NASNet-A. With CutOut , ENAS's error decreases to 2.89%, compared to 2.65% by NASNet-A. However, as discussed in Appendix B, our ENAS cells are trained for only 310 epochs, compared to 600 epochs by NAS. Sanity Check and Ablation Study. To understand the role of ENAS, we carry out two control experiments. In the first study, we uniformly at random pick a configuration of channels and skip connections and just train a model. As a , about half of the channels and skip connections are selected, ing in a model with 47.1M parameters and an error rate of 5.86%. This error rate is significantly worse than the models designed by ENASand has many more parameters. In the second study, we only train ω and do not update the controller. The effect is similar to dropout with a rate of 0.5 on both the channels and the skip connections. At convergence, the model has the error rate of 11.92%. On the validation set, the ensemble of 250 Monte Carlo configurations of the trained model could only reach 8.99% test error rate. We therefore conclude that the appropriate training of the ENAS controller is crucial for good performance. Neural Architecture Search (NAS) is an important advance that allows faster architecture design for neural networks. However, the computational expense of NAS prevents it from being widely adopted. In this paper, we presented ENAS, an alternative method to NAS, that requires three orders of magnitude less resources×time. The key insight of our method is to share parameters across child models during architecture search. This insight is implemented by having NAS search for a path within a larger model. We demonstrate empirically that the method works well on both CIFAR-10 and Penn Treebank datasets. The shared parameters ω between different recurrent cells thus consist of all the matrices DISPLAYFORM0,j, and W (h),j. The controller decides the connection j and the activation function f, for each ∈ {2, 3, ..., N}. The layers that are never selected by any subsequent layers are averaged and sent to a softmax head, or to higher recurrent layers. As in the case of convolutional models, to stabilize the training of ω, we add a batch normalization layer after the average of the layers that are not selected. B Details for CIFAR-10 Search Spaces B.1 Details on Search Space 1: ChannelsWe use a block size of S = 32, ing in C/S = 256/32 = 8 blocks per branch per layer. Each branch configuration has its own embedding and softmax head. To elaborate, this means that a time step in the controller RNN that predicts the configuration for any branch should have a softmax matrix of size H × (2 C/S − 1), where H = 64 is the hidden dimension of the RNN, and 2 C/S − 1 = 255 is the number of possible binary masks for that branch. Each branch also has an embedding matrix of size (2 C/S − 1) × H, from which the row corresponding to the sampled binary mask is selected and sent to the next time step. Layers 4 and 8 of our 12-layer network are max pooling layers with a kernel size of 2 × 2 and a stride of 2, and reduce each spatial dimension of the layers' outputs by a factor of 2. Within each group of 3 layers where the spatial dimensions of the layers remain constant, we connect each layer to all layers before it BID17. We use 3 × 3 convolutions with 48 output channels at all layers. The controller RNN for this search space has the same form as the controller RNN that is depicted in FIG2, with two modifications. First, each block has only 2 time steps (as opposed to 7 in the general search space): the time step that predicts the mask for the convolution of filter size 3 × 3, which we force to always activate all channels; and the anchor time step, which we allow to sample multiple previous indices. Second, our controller is thus allowed to form skip connections between arbitrary layers, but forming such connections between layers with different spatial dimensions would in compilation failures. To circumvent, after each max pooling in the network, we centrally pad the output so that its spatial dimensions remain unchanged. We perform a 3×3 convolution on the image to create the outputs for the first convolutional cell. After that, in the first 6 convolution cells, each separable convolution has 32 output channels. Each reduction cell is applied in the same way as the convolutional cell, with the only modification being each operation is applied with a stride of 2. When the cells are found, the final models (both with and without CutOut) are trained for 310 epochs, using the cosine learning schedule, where the reset cycle is originally set to 10 and then doubled after each reset. Additionally, we insert an auxiliary head at the layer immediately before the second application of the reduction cell BID35.
An approach that speeds up neural architecture search by 10x, whilst using 100x less computing resource.