DA-NAS: Data Adapted Pruning for Efficient Neural Architecture Search
Xiyang Dai Dongdong Chen Mengchen Liu Yinpeng Chen Lu Yuan
cs.CV




headings
5875  

 


















X. Dai et al.



Microsoft


DA-NAS: Data Adapted Pruning for Efficient Neural Architecture Search
    Xiyang Dai   Dongdong Chen   Mengchen Liu    Yinpeng Chen   Lu Yuan
    December 30, 2023
=======================================================================




Efficient search is a core issue in Neural Architecture Search (NAS). It is difficult for conventional NAS algorithms to directly search the architectures on large-scale tasks like ImageNet. In general, the cost of GPU hours for NAS grows with regard to training dataset size and candidate set size. One common way is searching on a smaller proxy dataset (, CIFAR-10) and then transferring to the target task (, ImageNet). These architectures optimized on proxy data are not guaranteed to be optimal on the target task. Another common way is learning with a smaller candidate set, which may require expert knowledge and indeed betrays the essence of NAS. In this paper, we present DA-NAS that can directly search the architecture for large-scale target tasks while allowing a large candidate set in a more efficient manner. Our method is based on an interesting observation that the learning speed for blocks in deep neural networks is related to the difficulty of recognizing distinct categories. We carefully design a progressive data adapted pruning strategy for efficient architecture search. It will quickly trim low performed blocks on a subset of target dataset (, easy classes), and then gradually find the best blocks on the whole target dataset. At this time, the original candidate set becomes as compact as possible, providing a faster search in the target task. Experiments on ImageNet verify the effectiveness of our approach. It is 2× faster than previous methods while the accuracy is currently state-of-the-art, at 76.2% under small FLOPs constraint. It supports an argument search space (, more candidate blocks) to efficiently search the best-performing architecture.









§ INTRODUCTION


Neural Architecture Search (NAS) has a great impact by automating neural network architecture design. The architecture is optimized for accuracy and efficiency (especially latency) under the constraints (, FLOPs, latency, memory). Recently, NAS has demonstrated the success in various deep learning tasks, such as image classification <cit.>, detection <cit.> and segmentation <cit.>.

Despite the remarkable results, conventional NAS algorithms <cit.> is prohibitively computation-intensive, especially directly on a large-scale task (, ImageNet <cit.>), which makes it difficult for making paretical industry impact. As a result, one common way is to utilize a smaller proxy data (, CIFAR-10) for searching, and then transfer to the large-scale target task (, ImageNet) <cit.>. Due to the domain gap (, resolution, class number) between proxy data and target task, these blocks optimized on proxy data are not guaranteed to be optimal on the target task, especially when taking accuracy and resource constraint into consideration. Thus, directly searching on the target dataset is essential to NAS.

Another common way is searching with a smaller candidate set <cit.>, which highly relies on the expert knowledge and indeed betrays the essence of NAS. In addition, too few candidate blocks are not beneficial to find a best-performing architecture under search constraints (, FLOPs, latency). Thus, an argument search space with more candidate blocks is always encouraged to boost the performance of NAS.

In this paper, we propose a simple and effective solution to the aforementioned limitations, called DA-NAS, which can directly search the architecture for large-scale target tasks in a more efficient manner, while allowing a large candidate set. The solution is based on our observation that the learning speed of blocks in deep neural networks is varied in different classes (for classification task). The blocks are learnt much faster in easy classes than in difficult classes. Besides, our study indicates that the performance of blocks in easy classes converges very quickly at the early training stage but needs more time in difficult ones. The discovery motivates a new data adapted pruning for NAS, which starts the search on a subset of target task (, easy classes), and gradually trims low performed blocks as the size of subset increases until we find the best blocks on the whole target dataset. To build the strategy, we may be able to group classes based on the easiness, and feed them progressively to reduce the computation cost.

We formulate NAS as a block-level pruning process, which is different from recent ProxylessNAS <cit.> that adopts a path-level pruning. Specifically, we directly train a supernet <cit.>, an over-parameterized network that contains all candidate paths. In the beginning of training, we train it on a subset of target task (only containing easy classes). During training, we progressively prune low performed blocks from our candidate set until we get a compact candidate set for searching on the whole dataset of target task. We consider a loss function with cost constraint which helps find an optimal architecture under search constraint (, FLOPs).

Comprehensive experiments and comparisons to existing methods demonstrate that DA-NAS can find an optimal architecture 2× faster and is also capable of finding a current best small FLOPs architecture at 76.2% on ImageNet within a highly complex search space (involving inverted residual block, shuffle block, squeeze-and-excitation block and more).

Our contributions can be summarized as follows:

  
  * DA-NAS is the first NAS algorithm that shows a close connection between block pruning and dataset scheduling. To our best knowledge, it is the first work to study the relationship between network learning and training data for NAS.  
  
  * We propose a progressive block-level pruning perspective for NAS, according to data adaption. It can search architecture on the large-scale target task much faster, and effectively enlarge the search space to achieve state-of-the-art performance.
  
  * The DA-NAS is convenient to use for various needs. It enables cost constraint in search, which is beneficial to practical industry impact. The inherent idea is also generalized to other tasks, like key-point localization.














 

















§ RELATED WORK



  
Efficient Network. Since the need of delopying deep neural networks into real application systems is increasing, efficient network has drawn a lot of attention from both academia and industry. Existing research about efficient network is often done from two broad aspects:  efficient network structure design <cit.>, or pruning/quantizing one given network structure <cit.>. In this paper, we focus on the former problem. For efficient network architecture design, many interesting approaches have been proposed. For example, Xception <cit.> proposes to decompose one normal convolution layer into one depth-wise and one point-wise convolutional layer, which is able to significantly reduce the computation FLOPs. Based on this design scheme, a lot of efficient networks have been further designed, such as MobileNet <cit.>, ShuffleNet <cit.>. Despite their success, designing such an efficient network is not that easy and can only be done by experts.    



  
Neural Architecture Search. Recently, NAS has drawn surging interests that study how to automatically design a better and efficient network structure with machine learning algorithms. Based on the searching strategy, existing NAS methods can also be roughly divided into two categories, , searching an efficient operator block <cit.> from scratch, or finding an optimal operator combination from a pre-defined efficient operator search space <cit.>. Compared to the former category, the latter category of approaches leverage a lot of design priors from human experts, so it is relatively easier to find an optimal network architecture. Our method belongs to the latter category. By contrast to existing methods whicj often regard data scheduling and architecture search as two independent parts, our method is the first that shows a close connection between both. By leveraging a new and efficient data scheduling mechanism, a progressive block-level search space pruning algorithm is further proposed. Our method is demonstrated to be more efficient and can search a better architecture given the same searching time.  



 
 















§ UNDERSTANDING NETWORK TRAINING PROCESS



In this section, we analyze the relationship between the performance of deep neural networks and the training data. These interesting observations will inspire our data adapted pruning for efficient neural architecture search.


 
 


















Observation 1. There exists some classes that are easy to learn (easy classes) while some classes are harder to learn (hard classes).


We start our analysis from exploring a typical network training process, , ResNet-34 trained on ImageNet. A matrix shown in Figure <ref> (a) visualizes the accuracy of distinct classes varies with more training iterations. Each row is certain a class and each column is training time (epoch =10,20,...,180). The value at each grid denotes the accuracy for each class. For a better visualization, we sort the matrix rows by row-wise variance of a matrix, namely, the variance of the accuracies of recognizing every class from each training epoch.





We find that the accuracy of some classes quickly converges and achieves its maximum (Figure. <ref> (b)); while some other classes gradually increase / fluctuate in the training (Figure. <ref> (c)). It indicates the learning speed for every class is different. Thus, we can group classes based on their easiness and feed them heuristically into training, following small-to-large data scheduling. Meanwhile, search using fewer categories at the beginning is a considerably easier task than the search using all categories in the end. This helps us progressively trim low performed blocks in the search space to reduce the search cost.











Observation 2. Neurons to recognize easier classes converge more quickly at the early training stage and their performance remains stable in the remaining training process. Neurons for hard classes need more time to be fully trained.




We study why the learning speed of different classes are not equal (in Observation 1). One possible reason is that various learning speed of neurons (, convolution kernels) makes learning speed of distinct classes different, since the final prediction of network is determined by a combination of neuron responses. To verify this reason, we visualize the relations between neurons and classes in increasing training epochs on Figure <ref> (b). The relation between a neuron and a class, used to distinguish the class from other classes, is computed by the neuron relevance measure proposed in <cit.>. Specifically, we only consider the neurons in the final convolutional layer (before FC-layer) since it represents the maximum semantics in neurons. We collect all the calculated relations into a matrix, where each row is a class and each column is a neuron. To be consistent with Figure <ref>, we use the same order of classes in rows, and further sort the matrix columns by column-wise maximum value (corresponding to the class most likely to be recognized by the neuron) of a matrix. Figure <ref> (a) show the sorting result of the matrix, where the top-left block corresponds to the easiest classes and the neurons that are most likely used to recognize these classes, and the right-bottom block corresponds to the hardest classes and corresponding neurons.

Figure <ref> (a) shows such a visualization corresponding to the last epoch, where classes of different easiness levels are learned by different neurons.
More interestingly, there is a “diagonal pattern” that neurons are distributed in balance across all the classes, summarized in Observation 3. It indicates that all the classes should be involved in the training for the best performance. In other words, directly learning on a large-scale dataset should yield better accuracy than on a smaller dataset. 

To further investigate the evolutionary pattern in the neuron-class relations, we visualize the matrix at three different training epochs (epoch=10,90,180) and select three representative blocks (corresponding to easy, medium, and hard classes) at each epoch, shown in Figure <ref> (b). In the first row, we observe that the neurons to recognize easy classes quickly converge and their performance keep stable in subsequent training. Compared with other two rows, the neurons learn faster on easy classes (stable on epoch=10) than that on medium classes (almost stable on epoch=90), and even much faster than hard classes (almost on epoch=180). The phenomena is summarized in Observation 2.









Observation 3. Different architecture of networks agree on similar easy/hard classes distribution. 


To further investigate whether above observation 1 and 2 are shared among other networks or unique for ResNet, we train and evaluate a bunch of state-of-the-art manually designed networks, including VGG <cit.>, ResNet <cit.>, MobileNet <cit.>, ShuffleNet <cit.> and more. For each class, we calculate the mean and variance of the running average on easiness histograms among multiple networks. Shown in Figure <ref> (a), the easiness histograms are well aligned with confusion matrix and can be used as an indicator for measuring how easy a network can distinguish a class from other classes. Shown in Figure <ref> (b), it is true that different networks agree on the similar distribution of easiness on classes. This phenomena enables us to effectively use data while increasing searching space. Shown in Figure <ref> (c), after sorted by easiness rank, the confusion matrix disentangles the hierarchy within classes. The mathematics definition for easiness is introduced in the following section. 




These observations inspire us to design a search space pruning strategy based on the easiness of classes and the learning status of neurons. At the beginning, we only feed in a small subset with easy classes to train all candidate blocks. Then, we can explicitly exclude unfavorable blocks that still struggle to learn or perform worse than others in easy classes. By sequentially feeding more hard classes until all the classes finally (the whole dataset), we can progressively trim low performed blocks step by step, as shown in Algorithm <ref>.











































































§ DATA ADAPTED NAS


Based on the analysis in Section. <ref>, the class easiness E_c for a class c is defined as: 



    P_i = N̂(d_i)    for    d_i ∈𝒟
       E_c,i = -∑ P_i log(P_i)    if    d_i ∈ c 
       E_c = iℋ(E_c,i)

where, 𝒟 is the training dataset (, ImageNet), N̂ is a network (, ResNet-34) fine-tuned on the dataset, and E_c is represented as a histogram ℋ(·) of entropy values of all the samples belonging to class c. For each training sample, since it is optimized towards a one-hot vector of the ground truth, the entropy of the network's output represents the effort of a network taking to distinguish the ground truth class from others. Then the histogram of these entropy values of a class represents the trend of easiness of all samples that belong to this class. As shown in Figure <ref>(a), the proposed measurement is well aligned with the confusion matrix and can be used to explore the trend of easiness on all classes and all training samples. Finally, for each class, we calculate the mean of on easiness histograms among multiple networks as our final data adaptation strategy.




 §.§ Expanding Search Space

In order to search any possible architecture in a search space, an over-parametered super network needs to be built first. Previous methods first define a set of candidate operators (, 3× 3 or 5× 5 depth-wise convolutions) 𝒪 = {o_1,…, o_k} and build the supernet layer by layer. Such approach largely limits all possible combinations of network architectures, and makes the micro-architecture design critical to the final search result.
Compared with previous method, we allow search in a large and diverse set of candidate blocks (, residual block, inverted residual block, shuffle block) ℬ = b_i, …, b_m applied over candidate operators (, depth-wise or normal 3× 3, 5× 5 convolutions) and effectively changed the super network to:

    N_l = ∑_j^m ∑_i^k b_j(o_i(x)) 
        N_l+1 = ∑_j^m ∑_i^k b_j(o_i(N_l))

Figure <ref> shows that our design can effectively combine multiple micro-architecture build blocks and simulate popular networks.



 §.§ Searching with Constrains

We followed the idea introduced by <cit.> to use Gumbel-Softmax to assist learning of the architecture:

    p ∼ GumbelSoftmax(a, τ) 
        N_l = ∑_j^m ∑_i^k p_i,jb_j(o_i(x))

where a is the architecture weight that we want to learn and τ is a pre-defined hyper-parameter to control the sharpness of Gumbel distribution.
To incorporate with search constrains (, FLOPS or hardware latency), we also compute the expected cost of a super network by:

    C_l = ∑_j^m ∑_i^k p_i,j𝒞(b_j(o_i(x)))

where 𝒞(·) is a function measuring the cost of a block.

The super network is first optimized towards classification loss to find the optimal weight:

    w = minℒ_cls (N(𝔻_train,a)).

Then it is optimized for architecture using the modified loss function with the cost constraint:

    a = minℒ_cls (N(𝔻_val,w)) ·log(C/β)^γ

where β is a scaling factor designed as target cost and γ is a factor to control the strength of incorporating cost constraints. 






 §.§ Training Strategy



The training of a NAS algorithm can be tedious and non-trivial. In our training strategy, we intelligently couple data scheduling and search space pruning together, as stated in previous sections. At beginning, we warm up the super network by training on only "easy" classes in order to convert each blocks into a well-trained state as fast as possible. Then we progressively add more classes from target dataset and, at same time, shrink the search space to speedup NAS to avoid falling in local minimal. The final optimal architecture is then automatically selected at the end of pruning. This strategy is further elaborated in Algorithm <ref>.

We intelligently combine data adaptation with network pruning in two ways:

    
  * We progressively introduce more categories in the architecture search. The search using fewer (100) categories at the beginning is a considerably easier task than the search using all (1000) categories in the end. This helps us progressively trim low performed blocks in the search space to reduce the search cost.
    
  * We also identify the easiness of the categories by voting from popular manually designed networks. We observe different network tends to learn similar "easy" categories quickly at the beginning. We start with a few "easy" categories at the beginning to speed up the convergence of supernet and hence further reduce the training cost.  


The benefit with our training strategy is three-fold:

    
  * It largely reduces the number of epochs and GPU hours required in training.
    
  * It eases the difficulty of tuning hyper-parameter, especially τ in Gumbel Softmax (Equation (<ref>)). τ controls the sample distribution and is usually critical to the final search result. Large τ turns to add randomness of sampling to help super network explore more variant of branch combinations; while lower τ trends to be more deterministic to branch selection and help super network select architecture quicker. It is necessary to balance these two factors to find optimal architecture after exploring large variants of combinations. Previous method coupled τ with learning rate and used an exponentially decaying schedule <cit.>. Unlike previous methods, τ in our training strategy is set to a fixed number, as the progressively pruning of search space works similar to reducing τ.
    
  * It picks the final architecture more confidently. Unlike previous methods that need sampling from the final architecture distribution to find the best candidate, our final optimal architecture can be directly picked by maximizing the architecture distribution, which further saves the computational cost. 








§ EXPERIMENT



 §.§ Setup



  
Datasets. 
We directly search architecture on the target dataset. For image classification task, we use the full ImageNet <cit.> dataset. We randomly select 50 images per class from the original training set to formulate a validation set. We then use the original validation set as a test set to report final experiment results. Besides, we also want to test our DA-NAS algorithm for key-point localization task. We use full COCO <cit.> key-point 2017 dataset. The original training set is divided into "trainminusminival" and "minival" for training and validation. Then the original validation set is used to report results. 



  
Search Spaces. 
We investigate two popular search spaces widely used in previous work <cit.> and their augments:

    
  * “Mobile”: The search space is based on MobileNet <cit.> micro-architectures. In our implementation, it contains three inverted residual blocks with expanded factor of 1,3,6 and two depth-wise convolution operators with 3× 3 and 5× 5 kernels. 
    
  * “Shuffle”: The search space is based on ShuffleNet <cit.> micro-architectures. In our implementation, it contains two shuffle blocks with different number of convolution layers and three depth-wise convolution operators with 3× 3, 5× 5 and 7× 7 kernels.
    
  * “Mobile+”: We expand "Mobile" by adding normal convolutions with 3× 3 and 5× 5 kernels into operators to increase the complexity and flops variation. 
    
  * “Shuffle+”: We expand "Shuffle" by adding normal convolutions with 3× 3 and 5× 5 kernels into operators to increase the complexity and flops variation. 
    
  * “Shuffle+Mobile”: We combine Shuffle spaces and Mobile spaces together. It is the major search space we use to find state-of-the-art architectures.
 



  
Implementation Details.
We implement our approach using Pytorch and run all experiments on a compute node with 4 V100 GPUs. For training, the super network is first warmed up with 10 epochs and followed by 3 steps of search with 20 epochs each. We use a search space pruning ratio 0.4 and 100, 300, 600, 1000 classes for each step respectively. For fine-tuning the searched architecture, we follow the training setup introduced by <cit.>, but pump up the initial learning rate to 0.5.








 §.§ Compared with State-of-the-art Methods

We first compared with two state-of-the-art methods, ProxylessNAS <cit.> and SinglePath <cit.>, which are claiming as fastest search methods on ImageNet. Since they report the performance and the search cost based on different criteria and hardware, in order to compare fairly, we re-implement these two methods based on public available code released by authors. As shown in Table <ref>, we are able to reproduce the reported performances. Then we run our methods with the exact same search space. It is obvious to see that our method is capable of finding competitive quality networks with much lower search cost. It significantly reduces the search cost by 39% and 65% respectively.

Next, to further investigate the lower bond of time cost needed for searching a proper architecture, we conduct an experiment with constrained search time and a enlarged search space. We double the operators in shuffle and mobile search spaces by introducing 3 × 3 convolution and 5 × 5 convolution. As shown in Table <ref>, our method is able to find the architecture with comparable accuracy to state-of-the-art methods by only half of the time needed in these methods.



Finally, we combine “Shuffle" and “Mobile" search spaces together to find the state-of-the-art architecture. Table <ref> shows the comparison between our method with existing popular NAS approaches <cit.>. We report their search costs directly from their public papers (although some of numbers we cannot reproduce locally). Compared with methods <cit.> only searched on a proxy dataset (, CIFAR), our method leads to a significant performance gain. It is worth noticing that the networks searched on smaller datasets suffered from sub-optimal performance when transferred to a large scale dataset. They also have difficulties in reducing FLOPs due to the fact that searching conducted on different resolutions of datasets causes different designs of architecture (such as pooling scales and number of layers). Compared with methods <cit.> that search directly on ImageNet, our method requires the least search cost  (138 GPU hours) to find best-performing architecture with the state-of-the-art accuracy (76.2%).






 §.§ Ablation Study

We first demonstrate that our data adapted pruning is efficient. We evaluate the effects of different data scheduling on pruning: from easy classes to all classes, from hard classes to all classes, use a small subset of classes solely and use all classes directly. As shown in Table <ref>, it is obvious that our "small (easy) → all" data adapted pruning is the most effective method, which is able to find the best network architecture with only 28% of the time compared to searching directly on all classes. This demonstrates that "from small to all" is very important and it yields 0.9 better at top-1 accuracy because of the difference of data amount. Then, starting from easy is better than hard, it yields another 30% compared to the improvement of using 10x more data, which is non-trivial.




Then, we show that our search space pruning is robust. We conduct experiments on three different search spaces: "Shuffle", "Shuffle+", "Shuffle+Mobile", which contain varieties of blocks and operators. As shown in Table <ref>, our method is robust enough to find the optimal architectures with nearly consistent accuracy and FLOPs using different search spaces. Besides, our search cost will accordingly increase as the search space is enlarged.



Finally, we analyze the necessity of each component in our proposed data adapted pruning method. We partially disable each key component to examine the influence. As shown in Table <ref>, our method full loaded largely reduces the search cost (from 307 GPU hours to 87 GPU hours) and yields the best searched architecture. This further proves the effectiveness of our method. 



 §.§ Transferring to Key-point Localization Task


We further apply our method to the key-point localization task to demonstrate the generalization ability. Following the setup in simple baseline <cit.>, we search a key-point localization architecture based on instance-level ground-truth. We modify our search space by attaching 3 levels of de-convolution layers at the end, consisting de-convolution operators with 4 × 4 kernel and 2, 4, 8 groups respectively. As shown in Table <ref>, our method is able to find a state-or-the-art architecture with significantly lower flops compared to manually designed methods <cit.> with competing performance and significantly speedup previous best NAS method <cit.>.   











 §.§ Visualization

We visualize our searched architectures in Figure <ref> with two interesting findings. First, it is obvious to see that shuffle block is more cost efficient than inverted residual block. As the FLOPs constrain looses, the network architecture tends to have more inverted residual block to further boost the performance. Second, inverted residual block with squeeze-and-excitation component (SE) <cit.> is more likely to be placed at where number of channels increases or resolution of input reduces. This indicates that it is more effective to model inter-dependencies between different features channels. These findings are consistent with the statements from <cit.>. Thanks to the advantage of combining complex search spaces together, our method is capable of finding interesting properties of different blocks. 



§ CONCLUSION

In this paper, we present a novel data adapted pruning approach that largely speeds up neural architecture search. Inspired on the findings that network tends to learn easy categories first at early stage observed from network training, we propose to progressively utilize more data based on the easiness of classes, while pruning search space at the same time. Our strategy solves the conflicts between the requirement of large-scale data for fine-grained architecture search and the linearly increasing search cost, and makes the NAS practical in real-world task. Experiments show that our method can find state-of-the-art architecture with noticeable lower cost compared to popular methods. Our method is the first to combine data scheduling and search space pruning. Although a full understanding of the best setup of data and search space is not investigated in this paper, it opens a very interesting direction on how to effectively search based on data. Future work will focus on exploring the better data & search space association and applying to much complicated task like object detection.


splncs04


