One-Shot Neural Ensemble Architecture Search by Diversity-Guided Search Space Shrinking

Introduction

The emergence of deep neural networks greatly relieves the need for feature engineering. Previous studies have shown that the design of neural network architecture is essential to the performance for varied tasks in computer vision. However, the number of possible architectures is enormous, making the manual design very difficult. Neural Architecture Search (NAS) aims to automate the design process. Recently, NAS methods have achieved state-of-the-arts on varied tasks such as image classification , semantic segmentation , object detection , \etc. Despite great progress achieved, most of the NAS methods focus on searching for optimal architectures of single models. However, the generalization ability and performance of single models are usually affected by different initialization, noisy data, and training recipe modification.

Model ensemble has been proved to be a universally effective method to build more robust and accurate models compared with single models. Implicit ensemble methods like Dropout , Dropconnect , StochDepth , Shake-Shake are already widely used in neural architecture design. On the contrary, although explicit ensemble methods like averaging, bagging, boosting, and stacking have been commonly adopted in large competitions and real-world scenarios. The use of explicit ensemble methods in designing efficient models is not fully explored due to the extra computation they brought.

Inspired by the effectiveness of ensemble, we propose to search for multiple models instead of one simultaneously to form a robust, accurate and efficient ensemble model. However, the combination of NAS and ensemble faces two challenges: (1) efficient search and supernet optimization over a large search space (2) reducing the extra complexity brought by model ensemble. Addressing these challenges, in this paper, we propose a one-shot neural ensemble architecture search (NEAS) approach searching for lightweight ensemble models.

To solve the first challenge caused by the enlarged space of ensemble models compared with single models, we propose a novel metric called diversity score to progressively drop inferior candidates during supernet training, thus reduce the difficulty of finding promising ensemble models. This metric explicitly quantifies the diversity between the operators, which is commonly believed to be a key factor in building models with better feature expression capability.

To solve the second challenge, we introduce the layer sharing mechanism to reduce the model complexity. We allow the ensemble components share some shallow layers and search for the best architectures of the shared layers together with the architectures of the rest layers. We further introduce a new search dimension called split point to automatically find optimal layers for sharing under a given FLOPs constraint.

Comprehensive experiments verify the effectiveness of the proposed diversity score and layer sharing strategy. They improve the ranking ability of trained supernet and lead to better searched architectures under same complexity constraint. The searched architectures generate new state-of-the-art performance on ImageNet . For instance, as shown in Fig. 1, our search algorithm finds a 314M FLOPs model that achieves 77.9% top-1 accuracy on ImageNet, which is 19% smaller and 1.6% better than EfficientNet-B0 . The architecture discovered by NEAS transfers well to downstream object detection task, suggesting the generalization ability of the searched models. We obtain an AP of 33.0 on COCO validation set, which is superior to the state-of-the-art backbone, MobileNetV3 .

In summary, we make the following contributions:

We propose a pipeline, NEAS, searching for diverse models under certain resource constraints. Our approach could search for both homogeneous and heterogeneous ensemble models.

We design a new metric, diversity score, to guide the shrinking process of search space. We evaluate its superiority on supernet training and the performance of searched models by enormous experiments.

We propose a layer-sharing strategy to reduce the complexity of ensemble models and enlarge the search space to search for an optimal split point.

We compare the searched architectures to state-of-the-art NAS methods on the image classification task and achieve state-of-the-art results. Furthermore, we evaluate our searched model on the downstream object detection task, showing their generalization ability.

Related works

Neural Architecture Search. NAS has shown its superiority to manual-crafted networks on varied vision tasks, such as image classification , semantic segmentation and object detection . Early NAS approaches search the architectures using either reinforcement learning or evolution algorithms . However, these approaches require training thousands of architecture candidates from scratch, leading to unaffordable computation overhead. Most recent works resort to the weight sharing strategy to amortize the searching cost. Those approaches train a single over-parameterized supernet and then share the weights across subnets. They could be further categorized as two types: path-based and gradient-based methods . Path-based methods sample paths in each iteration to optimize the weights of supernets. Once the training process is finished, the subnets can be ranked by the shared weights. On the other hand, gradient-based methods relax the discrete search space to be continuous, and optimize the search process by the efficient gradient descent.

Recent work NES proposes to search diverse architectures to form robust ensembles against distributional shift of the data. NES shows that the ensemble of different architectures performs better than fixed architectures and provides a new regularized evolution search algorithm for ensemble architecture search. Since NEAS searches for efficient and effective models and NES searches for models without considering the computation cost, we do not compare NES in our work.

Ensemble Learning. Ensemble methods are widely used to build stronger and robuster models than single models. . Strategies for building ensembles could be mainly divided into two categories. The first ones train different models independently and then apply ensemble methods to form a more robust model, such as boosting, bagging, and stacking . The other methods train only one model with specific strategies to achieve implicit ensemble . Different from the above methods, we perform explicit ensemble without separate training and search for diverse model architectures to build ensemble models with great feature expression ability.

Search Space Shrinking. Recent works have shown search space shrinking is effective in boosting the ranking ability of NAS methods, especially when the search space is huge. . These methods could be classified into different types according to their evaluation metrics. There are three basic types: accuracy-based, magnitude-based, and angle-based metrics. For example, PCNAS drop unpromising operators layer by layer using accuracy and shows that it improves candidate networks’ quality. AngleNAS uses the angles between weights of models to guide the search process. However, existing shrinking techniques only consider operators independently. Therefore, they can’t directly adapt to search for ensemble models. We design a new metric considering both the performance of single operators and the diversity across them.

Approach

In Section 3.1, we give the formulation of NEAS. In Section 3.2, we present the definition of the diversity score and the space shrinking pipeline. In Section 3.3, we introduce the layer sharing mechanism and the new search dimension Split Point. In Section 3.4, we give the detailed pipeline of NEAS which allows to search under different resource constrains. The overall framework is visualized in Fig. 2.

Given the search space $\Omega$ of single deep neural networks, denote $\mathcal{A}=\{\phi_{k}\in\Omega:k=1,\dots,K\}$ as a set of $K$ architectures with corresponding parameters $\mathcal{W}=\{\omega_{k}:k=1,\dots,K\}$, $\Phi(\cdot;\mathcal{A},\mathcal{W})$ as the ensemble model, and $\mathcal{S}=\Omega^{K}$ as the search space of ensemble models. The goal of NEAS is to find an optimal architectures set $\mathcal{A}^{*}$ that maximizes the overall validation accuracy. To reduce the search cost, we constrain $\Omega$ to a certain architecture family, specifically, the subnetworks induced by a predefined supernet. In our work, we specify $\Phi(\cdot;\mathcal{A},\mathcal{W})$ as:

We then formulate NEAS as a two-stage optimization problem like other one-shot methods (\eg, ). The first-stage is to optimize the weight of the supernet by:

where $\mathcal{L}_{\rm train}$ is the loss function on the training set, $W(\mathcal{A})$ means architectures in ${\mathcal{A}}$ inherit weights from $W$.

This step is done by uniformly sampling an ensemble architecture $\Phi$ from $\mathcal{S}$ and performing backpropagation to update the weight of the corresponding blocks in the supernet for each iteration. Please refer to Section 3.4 for details.

The second step is to search for an optimal architecture set $\mathcal{A}^{*}$ via ranking the performance based on learned weight $W_{\mathcal{S}}$ of supernet, which is formulated as

where $g$ and $C$ are the resource computation functions and the resource constraints. Typical constraints include FLOPs, parameters size, and run-time latency.

Since it is difficult to enumerate all ensemble architectures for evaluation, we resort to a specific $K$-path evolution algorithms to find the most promising one. The details are presented in Appendix B and Section 3.4.

2 Diversity-Guided Search Space Shrinking

Since we search directly for the ensemble models, the search space for each layer increases exponentially from $N$ to $A_{N}^{K}=\frac{N!}{(N-K)!}$ compared with single path methods, where $N$ is number of the alternative operators for each layer. The large search space causes inefficiency search and supernet optimization problem. Search space shrinking is a feasible solution to alleviate the problem by discarding inferior operators progressively with a specific metric. Since diversity plays a key role in building a robust ensemble model, we design a new metric to explicitly quantify the diversity across operators inspired by fixed-size determinantal point processing ($K$-DPP) , a popular sampling model with great ability to measure the global diversity and quality within a set. In the following section, we first define the diversity score of an operator combination and then present the diversity-guided search space shrinking pipeline.

Definition of Diversity Score. Assume we have an ensemble model $\Phi(.;\mathcal{A},W(\mathcal{A}))$, wherer $\mathcal{A}=\{\phi_{1},\phi_{2},\cdots,\phi_{K}\}$ consisting of $K$ different paths. Since we fix the depth of the search space, we can slice $\mathcal{A}$ into operator combinations by layer. Then, $\mathcal{A}$ can be reshaped as $\{h_{m}|h_{m}=(o_{1,m},o_{2,m},\cdots,o_{K,m}),m=1,2,\cdots,d\}$, where $m$ and $d$ are the index of the layer and number of total layers, $o_{i,m}$ denotes the operator on layer $m$ of the path $i$. Now our goal changes to find the optimal operator combination for each layer.

Let $v_{1},\cdots,v_{K}$ denote the feature maps output from the $K$ different paths $\phi_{1},\cdots,\phi_{K}$ of the ensemble model $\Phi(.;\mathcal{A},W(\mathcal{A}))$. We define the similarity $S_{i,j}^{m}$ of two operators $O_{i,m}$ and $O_{j,m}$ as expected the similarity between paths that contains the two operators, respectively:

where $1\leq p,q\leq K$, $\beta$ is a scaling factor, and the indicator function is defined as:

The quality of operator $O_{i,m}$ is computed by taking expected accuracy of paths containing it. The formal definition is:

where $\phi_{q},\phi_{p}\in\mathcal{A}$, $\rm{ACC}_{train^{\prime}}$ is the accuracy evaluated on a small part of training dataset.

In practice, we do not calculate the exact expectation of similarity matrix and quality matrix. Instead, we randomly sample a finite number of ensemble models and use the mean as an approximate of the expectation.

The diversity score of a certain operator combination $h_{m}$ of layer $m$ is defined as following:

where $L_{m}^{y}$ is the submatrix of $L_{m}$ that contains all operators of $h_{m}$. The trade-off between similarities and accuracy is controlled by the hyperparameter $\gamma$.

According to the the definition of diversity score, we have the following property: For $h_{m}$ and $h_{m}^{\prime}$ that are different by only the $i_{th}$ operator, if $S_{i,j}^{m}<S_{i^{\prime},j}^{m}$ for $j=1,2,\cdots,K$ and $r_{i}^{m}>r_{i^{\prime}}^{m}$, then

This property suggests that the metric will drop similar and unpromising operator combinations while keep diverse and accurate operator combinations. We refer to Appendix A for a proof.

Diversity-Guided Search Space Shrinking. Based on the diversity score, we present Algorithm 1 to describe the diversity-guided search space shrinking pipeline shown in middle of Fig. 2. Note that during the shrinking process, at least one operator combination is preserved, since our method does not change the connectivity of the supernet.

3 Layer Sharing Among Ensemble Components

The challenge of potential massive complexity of searched ensemble models is handled by the layer sharing mechanism. This mechanism is inspired by several recent studies . These works find that both the same neural architectures with different initialization and different architectures learn similar features in their lower layers. Therefore, we consider to share the shallow layers of different ensemble components. We propose to search for diverse ensemble components with shared shallow layers and different deep layers to reduce the computation cost. To automatically find which layers should be shared, we design a new search dimension called split point. The split point defines where the ensemble model will have heterogeneous architectures. It also handles the trade-off between diversity and computation constrain. A comparison between the architectures searched by NEAS and other NAS methods such as is presented in Fig. 3.

4 Neural Ensemble Architecture Search

As state in Section 3.1 and in Fig. 2, NEAS includes two sequential phases: K-path supernet training with diversity-guide search space shrinking, and K-path evolution search.

Phase 1: K-Path Supernet Training with Diversity-Guide Search Space Shrinking. For each training iteration, an ensemble model $\Phi(.;\mathcal{A},W(\mathcal{A}))$ is randomly sampled. In specific, we randomly sample the split point $s$, the architecture of sharing layers $\mathcal{A}_{sharing}=\{o_{1},o_{2},\cdots,o_{s}\}$, and the operator combinations $\mathcal{A}_{split}=\{h_{s+1},h_{s+2},\cdots,h_{d}\}$ for the rest of layers from the shrunk search space. The loss $\mathcal{L}_{i}$ of each path $\phi_{i}$ is computed independently while the backpropagation is performed using the combined loss $\mathcal{L}=\sum^{K}_{i}\mathcal{L}_{i}$ to update the weights of corresponding blocks in the supernet. Following this updating process, the whole network is still trained in an end-to-end style. After training the supernet for several epochs, we follow the steps in Algorithm 1 to shrink the search space. The shrinking and training are conducted alternatively.

During inference, these selected paths make predictions independently, and our ensemble network’s output is the average of predictions from all paths.

Phase 2: K-Path Evolution Search. After obtaining the trained supernet, we perform evolution search on it to obtain an optimal ensemble model. These models are evaluated and picked according to the manager of the evolution algorithm. It is worth noting that, before evaluating an ensemble model, we first need to recalculate the batch normalization (BN) statistics for each block. This is because, during the supernet training, the BN statistics of different blocks are optimized simultaneously. These statistics are usually not applicable to the subnets. We randomly extract a part of the ImageNet training set to recalculate the BN statistics.

At the beginning of the evolution search, we pick $N_{\rm seed}$ random architecture as seeds. The top $k$ architectures are picked as parents to generate the next generation by crossover and mutation. In one crossover, two randomly selected candidates are picked and crossed to produce a new one during each generation. We drop the architecture got by crossover if the corresponding architecture is not in the shrunk search space or exceeds the FLOPs constraint. In one mutation, a candidate mutates its split point with a probability $P_{s}$. If the split point increases, the number of sharing layers increases with the same number. We randomly pick one path and move its corresponding architectures to the sharing architecture. Otherwise, if the split point decreases, we cut the sharing architecture and add it to each path’s architecture. At last, the candidate mutates its layers with a probability of $P_{m}$ to produce a new candidate. It is worth noting that the operation combinations are only picked from the shrunk search space. We perform crossover and mutation several times to generate new candidates. We generate some random architectures after crossover and mutation to meet the given population demanding. We provide the detailed algorithm in the Appendix B.

Experiment

In this section, we first give details of our search space and implementation. We then present ablation studies dissecting our method, followed by a comparison with previous state-of-the-art NAS methods. At last, we evaluate the generalization ability and robustness of the searched architecture on COCO object detection benchmark.

Search Space. Consistent with previous NAS methods , our search space includes a stack of mobile inverted bottleneck residual blocks (MBConv). We also add squeeze-excitation modules to each block following EfficientNet and MobileNetV3 . For details, there are 7 basic operators for each layer, including MBConv with kernel sizes of 3,5,7, expansion rates of 4,6 and skip connect for elastic depth. The split point space is set to range (9, 20) to handle different complexity constrains. In total we have $7^{20K}\times 12\geq 7\times 10^{33}$ ($K\geq 2$) architectures, which is much larger than most NAS methods. A more detailed description of search space could be found in Appendix A.

Supernet Training. We train the supernet for 120 epochs using the settings similar to SPOS : SGD optimizer with momentum 0.9 and weight decay 4e-5, initial learning rate 0.5 with a linear annealing. The shrinking process is conducted every 20 epochs. The number of operators dropped each time is empirically set to 20. $\beta$ in the computing the similarity matrix is set to 1e-3 according to experimental results.

Evolution Search. We set the population $N_{\rm seed}$ of evolution search to 50 with the size of top candidates pool $k$ equals to 10. The number of generations is 20. $P_{s}$ and $P_{m}$ are both 0.1. The number of candidates performs mutation and crossover are set to 25 in each generation. We recalculate the BN statistics on a subset of ImageNet.

2 Ablation Study

Effectiveness of Diversity Score. We set the baseline as NEAS without diversity-guided shrinking. In addition, we compare the diversity score with the accuracy metric to further verify its efficacy. Since the accuracy-based methods only consider the accuracy of single operators in each layer. We adapt the definition of accuracy to the accuracy of operator combinations. Other methods like Angle-based metric can not easily adapt to search for ensembles.

We first perform correlation analysis to evaluate whether the training process with diversity shrinking can improve the ranking ability of supernet. We randomly sample 30 subnets and calculate the rank correlation between the weight sharing performance and the true performance of training from scratch. Training many such subnets on ImageNet is very computationally expensive. We follow the setting of Cream , which constructs a subImageNet dataset consisting of 100 classes randomly sampled from ImageNet. Each class has 250 training images and 50 validation images. We use Kendall Tau to show the ranking capacity of supernet. The second column of Table 2 suggests that our diversity score effectively helps supernet to rank the ensemble architectures in the supernet.

We also retrain the searched architectures by the three methods under the same FLOPs constraint. The top-1 and top-5 accuracy results on the ImageNet dataset are shown in the third and fourth columns in Table 2. We could see that the diversity-guided shrinking is 0.6% better than the baseline and 0.7% better than the accuracy-based method. We further compare the average accuracies of the architectures in the last generation of evolution search, displaying in the fourth columns. Our diversity-guided shrinking surpass the baseline and accuracy-based method by 0.5% and 1.1% top-1 accuracy on ImageNet in the supernet. The results suggest that the diversity score helps remove unpromising candidates and enhance the convergence of supernet.

Impact of Heterogeneous Path Architectures. Ensembling models of homogeneous (homo) architectures are known to be an effective way of building powerful models . We here compare the ensemble models of homogeneous and heterogeneous architectures to show the importance of heterogeneous ensemble. We use our searched two-path ensemble model as the baseline. Then we mirror one path of the searched architecture to form two homogeneous ensemble models for comparison. Fig. 4 gives the visualization of the final hidden features of baseline and the homogeneous network fine-tuned on CIFAR-10. We can see that the homo paths have a similar feature distribution. However, the hetero paths have varied feature distribution and a clearer margin between the clusters.

In table 3, we compare the performance of these three models on ImageNet. This table shows an interesting fact that even the stand-alone performance of homo paths are better than hetero. However, the performance of the homo ensemble is worse than the heterogeneous one, indicating that the two paths of the searched model are complementary.

Impact of Layer Sharing. Layer sharing plays a significant role in reducing the complexity of an ensemble model. Here, we explore the effectiveness of layer sharing. The baseline is the ensemble model with no shared layers searched by our method. In Table 4, we could see that layer sharing will help to reduce the complexity of ensemble models largely while keeping outstanding performance. Besides, we observed that in our searched models, the larger model attempts to share fewer layers. One reason could be that the feature expression ability of stand-alone paths in larger models is already strong since it is more complicated. Therefore, they prefer to share fewer layers and get more diverse paths.

Impact of Number of Paths for Ensemble. The number of paths $K$ used to form the ensemble model is a hyperparameter we define at first. We compare the performance of the searched model under the mobile setting ($\leqslant$600M FLOPs) using different $K$. From Table LABEL:tab:paths, we can see that when the number of paths is equal to 2, we achieve the best results. One likely reason could be that if a network has too many paths, each path’s stand-alone feature expression ability decreases a lot due to complexity constraints.

Impact of Search Algorithm. Random search is known to be a competitive baseline in NAS methods. We compare random search with evolution search to evaluate the effectiveness of evolution search. We demonstrate the performance of architectures using the weights inherited from supernet on the validation dataset during the search. Top 50 candidates until the current iteration are depicted at each iteration. Fig. 5 illustrates that evolution search is better for searching on supernet.

3 Comparisons with State-of-the-Art Methods

Table 1 presents the comparison of our method with state-of-the-arts under mobile settings on ImageNet. It shows that when considering models with FLOPs smaller than 600M, our method consistently outperforms the recent MobileNetV3 and EfficientNet-B0/B1 . In particular, NEAS-L achieves 80.0% top-1 accuracy with only 574M FLOPs, which is 160M FLOPs smaller and 0.8% better than EfficientNet-B1. NEAS-M obtains 79.5% top-1 accuracy with 472M FLOPs. NEAS-S achieves 77.9% accuracy using only 314M FLOPs, which is 0.8% better and 19% smaller than EfficientNet-B0. We also provide results of other state-of-the-art NAS methods in Table 1. It is worth noting that some NAS methods like OFA , BigNAS , DNA use knowledge distillation to boost the training process and also improve the accuracy of searched models. However, even compared with these methods, our searched ensemble architectures, which do not use knowledge distillation, still achieve superior performance.

4 Generalization Ability and Robustness

To further evaluate the generalization ability of the architectures found by NEAS, we transfer the architectures to the downstream COCO object detection task. We use the NEAS-S (pre-trained 500 epochs on ImageNet) as a drop-in replacement for the backbone feature extractor in RetinaNet and compare it with other backbone networks. We perform training on the train2017 set (around 118k images) and evaluation on the val2017 set (5k images) with 32 batch sizes using 8 V100 GPUs. Following the settings in , we train the detection model with 12 epochs, an initial learning rate of 0.04, and multiply the learning rate by 0.1 at epochs 8 and 11. The optimizer is SGD with 0.9 momentum and 1e-4 weight decay. As shown in Table 6, our method surpasses MobileNetV2 by 4.7% using similar FLOPs. Compared with MnasNet , our method utilizes 7% fewer FLOPs while achieving 2.5% higher performance, suggesting the architecture has good generalization ability when transferred to other vision tasks.

Conclusion

In this work, we propose a novel approach to search for lightweight ensemble models based on one-shot NAS. We design a new metric, called diversity score, to guide search space shrinking. We further use the layer-sharing mechanism to reduce the complexity of ensemble models and introduce a new search dimension, called split point, to handle the trade-off between diversity and complexity constraint. Extensive experiments demonstrate that the proposed new metric is effective and improves the weight sharing supernet’s ranking ability. Our searched architectures do achieve not only state-of-the-art performance on ImageNet but also have great generalization ability and robustness.

References

Appendix A

In this appendix, we include: (I) proof of the property stated in Section 3.2, (II) the detailed supernet structure and search space.

In this section, we show a more detailed formula of the property stated in Section 3.2 and the proof of the property.

Property: Assume that $h_{m}:=(o_{1,m},\cdots,o_{j,m},\cdots,o_{K,m})$ and $h_{m}^{\rm{}^{\prime}}:=(o_{1,m},\cdots,o_{j,m}^{\rm{}^{\prime}},\cdots,o_{K,m})$ are different only by $j_{th}$ operator. Denote the indexes of operators in $h_{m}$ and $h_{m}^{{}^{\prime}}$ as $\sigma_{1},\sigma_{2},\cdots,\sigma_{K}$ and $\sigma_{1}^{\rm{}^{\prime}},\sigma_{2}^{\rm{}^{\prime}},\cdots,\sigma_{K}^{\rm{}^{\prime}}$. If $S_{i,k}^{m}<S_{i^{\rm{}^{\prime}},k}^{m}$ for $k=1,2,\cdots,K$ and $r_{i}^{m}>r_{i^{\rm{}^{\prime}}}^{m}$, then we have:

where $\sigma_{j}$ and $\sigma_{j}^{{}^{\prime}}$ equal to $i$ and $i^{{}^{\prime}}$.

Proof: Given the property of matrix determinant and definition of $L_{m}^{y}$, the diversity score of $h_{m}$ could be expressed as:

where $S_{m}^{y}$ are the corresponding submatrixs of $h_{m}$ in $S_{m}$.

where $B_{i}(k,l)$ is the entry in row $k$ column $l$. We then prove the following inequality by induction:

For $i=0$, consider matrix $A$ defined as follow:

Given the assumption that $S_{i,k}^{m}<S_{i^{\rm{}^{\prime}},k}^{m}$ for $k=1,2,\cdots,K$, we have ${S_{m}^{y}(1,j)}<S_{m}^{y^{{}^{\prime}}}(1,j)$. Then we could get $A$ is a positive define matrix easily using the definition of positive define matrixs. Regarding $A$ and $B_{0}$ are both semi-positive define matrix, we have following statement using Oppenheim’s inequality:

where $A\circ B_{0}$ is the Hadamard product (element-wise product) of $A$ and $B_{0}$. Besides, $B_{1}$ is also a semi-positive define matrix according to Schur product theorem.

For $i=1,2,\cdots,K-1$, it is easy to construct $A$ with similar definition like above and get the statement that ${\rm det}(B_{i})\leq{\rm det}(B_{i+1})$. Now, combining the chain of inequality, we have:

Using Eq. (11)(16), the property holds easily.

A-II: Supernet Structure and Search Space

In this section we give the detailed supernet structer and space of the new dimension Splint Point.

Appendix B

In appendix B, we show the detailed evolution algorithm, with the detailed algorithm of $K$-path evolution search below. Specific steps of ${\rm Crossover},{\rm Mutation}$ are presented in Section 3.4.