Neural Network Pruning by Cooperative Coevolution

1 Introduction

Convolution neural networks (CNNs) have achieved great success in computer vision tasks, such as image classification [He et al., 2016] and object recognition [Liu et al., 2020]. However, modern CNNs are typically too computationally intensive to be deployed on resource-constrained applications. To address this issue, a variety of methods have been proposed to reduce their computational costs [Hinton et al., 2015; Han et al., 2016]. Among them, neural network pruning has achieved impressive results in various applications by removing redundant parameters while keeping a high accuracy, as modern CNNs are usually overparameterized.

Despite its broad application prospects, the large number of parameters of CNNs poses a great challenge to neural network pruning. Performing the pruning process on the filter level can alleviate this issue to some extent. However, most previous filter pruning methods rely heavily on some criteria or auxiliary modules, which are used to measure the importance of each filter, but are usually derived from the experience and knowledge of experts. Thus, an automatic framework is essential to facilitate the application of filter pruning on various architectures and data sets.

∗This work was supported by the NSFC (62022039, 62106098), the Jiangsu NSF (BK20201247), and the CAAI-Huawei MindSpore Open Fund. Chao Qian is the corresponding author. Supplementary materials are available at https://arxiv.org/abs/2204.05639.

Filter pruning can be generally formulated as a complex optimization problem with the aim of searching for a good subset of the original filters to be retained such that the resultant pruned network has a low computational cost while keeping a high accuracy. Evolutionary algorithms (EAs) [B¨ack, 1996] are a kind of general-purpose heuristic randomized optimization algorithms, inspired by natural evolution. They have been naturally applied to solve the optimization problem of pruning, making the process automatic [Yao, 1999]. However, unlike the multilayer perceptrons of earlier years, the large number of filters of modern CNNs implies a large search space, making EAs difficult to obtain a satisfactory solution within a limited computational overhead. As a consequence, existing EA-based pruning methods mainly take compromises when applied to modern CNNs. One way is to apply EAs to optimize the hyper-parameters (e.g., the pruning ratio of each layer [Li et al., 2018]) of existing pruning methods with expert knowledge. Others often use indirect encoding methods to compress the search space partly [Zhou et al., 2021; Fernandes and Yen, 2021], which may, however, degrade the performance due to the loss of information.

To solve the essential large-scale neural network pruning problem, this paper proposes a novel Cooperative CoEvolution algorithm for Pruning (CCEP). Cooperative coevolution uses the idea of divide-and-conquer, and has been shown to be effective for solving large-scale optimization problems [Hong et al., 2019]. Although cooperative coevolutionary EAs have been proposed before [Ma et al., 2019], none of them has been designed with the explicit purpose to solve neural network pruning problems. The main idea of CCEP is to use the strength of cooperative coevolution to overcome the largescale issue in neural network pruning, and meanwhile utilize the property of neural networks for the non-trivial separation issue of cooperative coevolution. Specifically, considering the characteristics of forward propagation that features are processed layer by layer, CCEP divides the original search space by layer because the impact of removing a filter is mainly related to whether the other filters in the same layer can retain the representation ability.

Experiments using ResNet and VGG on CIFAR-10 and ImageNet show that the proposed CCEP can achieve a competitive performance with a number of state-of-the-art pruning methods which require experts to design good criteria or auxiliary modules. Furthermore, compared with previous automatic EA-based pruning methods, CCEP can achieve both larger pruning ratio and smaller accuracy drop. Note that CCEP can be flexibly applied to different network architectures and data sets, since no complex rules or modules are employed and the optimization process is highly decoupled with the architecture. Due to the advantage of cooperative coevolution, CCEP can also be easily parallelized, which is friendly to the application in practice.

2 RelatedWork

2.1 Neural Network Pruning

Neural network pruning on CNNs has been widely studied in the past decade. The methods can be generally divided into non-structured and structured pruning, where the former is directly conducted on the weights and the latter is usually on the basic structured cells such as convolution filters. Nowadays, filter pruning has prevailed since it is friendly to most existing hardware and software frameworks.

Based on how to indicate the filters to be pruned, the mainstream filter pruning methods can be further categorized into criteria-based and learning-based methods. Criteria-based methods design some criteria artificially to identify unimportant filters and prune them. For example, L1 [Li et al., 2017] prunes the filters with smaller l1-norm weights. FPGM [He et al., 2019] calculates the geometric median of the filters in each layer and prunes the neighbouring filters. HRank [Lin et al., 2020] locates the low-rank features and prunes the corresponding filters. ThiNet [Luo et al., 2019] prunes the filters by minimizing the reconstruction error. However, it is not easy to decide a proper criterion as well as the pruning ratio of each layer, which usually require rich experience and plenty of trials of experts. Learning-based methods use auxiliary modules to model the importance of filters in each layer and prune the neural network accordingly. For example, AutoPruner [Luo and Wu, 2020] uses learnable indicators on filters as the reference to prune. BCNet [Su et al., 2021] introduces a bilaterally coupled network to efficiently evaluate the performance of a pruned network, and performs the pruning based on this surrogate model. Such methods can liberate the trials on designing proper criteria, but usually lead to a complex pruning framework and deteriorate the extendibility.

2.2 Pruning by Evolution

Since the 1990s, EAs have been applied to prune artificial neural networks automatically [Yao, 1999], with the aim of removing unimportant neural cells and connections while keeping a high accuracy. As the scales of neural networks were small, EAs could be easily applied to achieve a good performance. However, in recent years, the architectures of neural networks have become more and more complex and large, hindering the direct application of EAs, since the large search space makes EAs hard to produce a good pruned network in acceptable running time.

The current EA-based pruning methods often search in a compressed filter space, e.g., DeepPruningES [Fernandes and Yen, 2021] shares an encoding in different layers, and ESNB [Zhou et al., 2021] uses block-level search. Instead of pruning neural networks directly, EAs are also applied to tune the hyper-parameters of existing pruning methods, e.g., OLMP [Li et al., 2018] searches a proper pruning threshold of each layer for layer-wise magnitude-based pruning methods. However, all these compromised strategies may lose useful information, leading to a less-satisfactory performance.

2.3 Cooperative Coevolution

Cooperative coevolution [Potter and Jong, 2000] is a famous evolutionary framework that has been shown suitable for large-scale optimization. It uses a divide-and-conquer approach to decompose a large-scale problem into several small-scale subcomponents and evolve these subcomponents cooperatively. A number of approaches have been proposed to incorporate the cooperative coevolution framework to improve the performance of EAs [Ma et al., 2019]. However, none of them is designed with the explicit goal of being able to solve neural network pruning problems. Furthermore, due to different properties of problems, it will often lead to a bad performance if applying a decomposition strategy designed for one problem directly to another. In this work, we adapt cooperative coevolution to neural network pruning for the first time, and employ a decomposition strategy based on the characteristics of forward propagation of CNNs.

3 The CCEP Algorithm

Let Φ denote a well-trained CNN with n convolution layers {L1,L2, . . . , Ln}, where Li indicates the ith layer and contains li filters. The aim of neural network pruning is to determine a subset of filters in Φ for removal so that the resulting pruned network has maximum accuracy and minimum computational cost. Let σ = {σij | σij ∈ {0, 1}, i ∈ {1, 2, ..., n}, j ∈ {1, 2, ..., li}}, where σij denotes whether the jth filter (denoted as Lij) in the ith layer of the network Φ is retained. That is, if σij = 1, the filter Lij is retained, otherwise it is removed. Thus, a vector σ naturally represents a pruned network Φσ = ⋃ni=1 ⋃li j=1 σijLij. When σij equals to 1 for any i and j, Φσ is actually the original network Φ.

Under the solution representation based on vector σ, neural network pruning can be formulated as an optimization problem that maximizes the accuracy and minimizes the computational cost of a pruned network Φσ simultaneously. Using the number of FLoat point OPerations (FLOPs), which is a common metric, to measure the computational cost, the pruning problem can be formally described as

This is essentially a large-scale optimization problem, as a deep CNN usually contains many filters, i.e., ∑ni=1 li is large. To solve the problem, a novel algorithm based on cooperative coevolution named CCEP, is proposed. The main idea is to make use of the divide-and-conquer technique applied in the cooperative coevolution framework, but transferring it to the context of neural network pruning. Despite cooperative coevolution has achieved impressive success in large-scale optimization, it has been reported that it would have a poor performance in non-separable problems if a proper decomposition strategy is not given [Ma et al., 2019]. As the filters in CNNs are usually highly related, the problem of neural network pruning is inherently non-separable. To solve this issue, a decomposition strategy based on the specific characteristics of typical CNNs is used in CCEP. Specifically, considering that the features are commonly processed layer by layer during the forward propagation of a CNN, the impact of removing a filter mainly depends on whether the other filters in the same layer can retain the representation ability. Thus, a natural strategy is to decompose the search space by layer. That is, the vector σ of decision variables is split into n groups, where ∀i ∈ {1, 2, ..., n}, the ith group corresponds to the ith layer and contains li variables {σi1, . . . , σili }. After that, CCEP coevolves n subpopulations representing these groups, each of which is optimized with a separate EA. It is worthy noting that CCEP is highly decoupled with the architecture of the original network, and thus can be applied to different networks flexibly and extended easily. Details of the framework of CCEP and the EA in each group are described below.

3.1 The Framework of CCEP

The framework of CCEP is shown in Algorithm 1. It employs an iterative prune-and-finetune strategy and finally outcomes a set of pruned networks with different pruning ratios for user selection. During each iteration, the algorithm works as follows. At the beginning, it splits the candidate filters to be pruned into n groups by layer in line 4 of Algorithm 1. Once the groups are created, the algorithm optimizes these groups in parallel in line 5. A separate EA is employed for each group, and it will continue until the stop condition specified in the EA is reached and outcome an individual representing the specific pruned layer. After that, a collaboration among these groups takes place in line 6, i.e., a complete pruned network will be created by splicing the n resultant pruned layers in their intrinsic order. At last, the algorithm will perform a finetune process to recover the accuracy of the obtained complete pruned network in line 7. An illustration of one complete coevolution process is shown in Figure 1. The finetuned pruned network Φ′ will be preserved into the archive A in line 8, and used as the base network Φ0 in line 9 for the next iteration. After running T iterations, the pruned networks in the archive A are output in line 12.

3.2 Details of the EA in Each Group

Generally, the EA in each group follows the typical evolutionary framework. It starts by initializing a subpopulation for the current group, and then evolves the subpopulation iteratively by generating and evaluating new individuals, and selecting better individuals to remain in the next generation. When terminating, the EA selects an individual from the final subpopulation and outcomes the corresponding pruned layer. The whole process is shown in Algorithm 2 and Figure 2.

Algorithm 1 CCEP framework

Input: A well-trained CNN Φ, maximum iteration T Output: A set of pruned networks with different sizes Process:

• 1: Set the base network Φ0 = Φ;
• 2: Let A = ∅, and i = 0;
• 3: while i < T do
• 4: Group the network Φ0 by layer;
• 5: Apply an EA in each group in parallel to obtain specific pruned layers, as shown in Algorithm 2;
• 6: Generate a complete pruned network by splicing all pruned layers in their intrinsic order;
• 7: Finetune the complete pruned network;
• 8: Add the finetuned network Φ′ into A;
• 9: Set Φ0 = Φ′ ;
• 10: i = i +1
• 11: end while
• 12: return the pruned networks in A

Concretely, the subpopulation is initialized with m individuals in line 1 of Algorithm 2. The first individual is created by the vector with all 1s, denoted as I0, to encourage a conservative pruning. The other m- 1 individuals are generated by applying the following bit-wise mutation operator with a mutation rate p1 on I0. Specifically, given an individual, the bit-wise mutation operator flips each bit of the individual with some probability (called mutation rate) independently until all bits have been tried or an upper bound r on the pruning ratio that limits the maximum number of pruned filters has been met. That is, the number of 0s (i.e, the number of pruned filters) of the generated individual should be no larger than |I0| × r, where |I0| is the number of filters contained by the ith layer of the current base network, preventing the pruning from being too violent. A detailed explanation of the bit-wise mutation operator is provided in the supplementary material.

In each generation of Algorithm 2, an offspring individual is generated by applying the bit-wise mutation operator with a mutation rate p2 on a parent individual randomly selected from P, and this process is repeated independently to generate m offspring individuals in line 4. When evaluating an offspring individual in line 5, which corresponds to a single

Algorithm 2 EA in each group

Input: The ith layer, population size m, data set Ds, mutation rates p1, p2, ratio bound r, maximum generation G

Output: A pruned layer

Process:

• 1: Initialize a subpopulationP with I0 andm-1 individuals generated from I0 by bit-wise mutation with p1 and r;
• 2: Let j = 0;
• 3: while j <G do
• 4: Generate m offspring individuals, each of which is generated by randomly selecting a parent individual from P and conducting bit-wise mutation with p2 and r on the parent individual;
• 5: Calculate the accuracy of the m individuals on Ds as well as their FLOPs;
• 6: Set Q as the union of P and the m individuals;
• 7: Rank the individuals in Q by accuracy and FLOPs;
• 8: Select the topm individuals and use them to update P;
• 9: j = j +1
• 10: end while
• 11: Conduct the final individual selection;
• 12: return the pruned layer w.r.t. the selected individual

pruned layer, a complete network is first formed by obtaining other layers from the base network of the current iteration and splicing them with the current pruned layer in their intrinsic order, as shown in Figure 3. The resultant complete network is evaluated in terms of accuracy, which is conducted on a small randomly sampled data set Ds to improve efficiency, and FLOPs. The results are assigned back to the individual under evaluation. After that, the m offspring individuals and the individuals in the current subpopulation P will be merged and ranked in lines 6-7, and the top m individuals will be selected to form the new subpopulation for the next generation in line 8. For the ranking, all individuals are ranked by their accuracy descendingly, and for the individuals with the same accuracy, the one with fewer filters is ranked higher. Note that to reproduce offspring individuals, only the simple bitwise mutation operator is used, but the experimental results in Section 4 have shown that it is good enough. Using more sophisticated operators (e.g., crossover operators) is expected to further improve the performance.

After running G generations, the final individual selection will be carried out. Two strategies are considered. One is to always select the top-ranked individual in the final subpopulation, called strategy Sela. The other strategy called Selb, is to select the top-ranked one except the individual with all 1s. That is, if the top-ranked individual in the final subpopulation has all bits equal to 1 (i.e., does not prune any filter), the strategy Selb will select the runner-up one. Selb can be used to speed up the whole pruning process while mildly sacrificing accuracy, which is useful in complex problems. The influence of these two strategies will be examined in the experiments.

4 Experiments

The experiments are conducted from two aspects. The first is to compare CCEP with existing pruning methods, including not only state-of-the-art pruning methods which require experts to design good criteria or auxiliary modules, but also automatic EA-based pruning methods. The second is to visualize the architecture of the pruned networks, and examine the effectiveness of introducing the pruning ratio bound r in mutation and the influence of hyper-parameters of CCEP.

Two classic data sets CIFAR10 [Krizhevsky and Hinton, 2009] and ImageNet [Russakovsky et al., 2015] for image classification are used for the examination. Two typical networks with different architectures are examined, i.e., VGG [Simonyan and Zisserman, 2015] and ResNet [He et al., 2016]. Following the common settings, the pruning is on all convolution layers for VGG, while it is on the first convolution layer of the normal residual blocks and the first and second convolution layers of the bottleneck blocks for ResNet.

The methods for comparison include six typical criteriabased pruning methods: L1 [Li et al., 2017], SFP [He et al., 2018a], FPGM [He et al., 2019], ThiNet [Luo et al., 2019], HRank [Lin et al., 2020] and ManiDP [Tang et al., 2021]; seven learning-based methods: AMC [He et al., 2018b], GAL [Lin et al., 2019], MetaPruning [Liu et al., 2019], LFPC [He et al., 2020], Pscratch [Wang et al., 2020], BCNet [Su et al., 2021] and GReg [Wang et al., 2021]; and two EA-based methods: DeepPruningES [Fernandes and Yen, 2021] and ESNB [Zhou et al., 2021]. All the results of the pruning ratio of FLOPs and accuracy are obtained directly from their original reports.

4.1 Experiments on CIFAR-10

CIFAR-10 has 50K images in the training set and 10K images in the test set, with the size of 32×32 for 10 categories. ResNet-56, ResNet-110 and VGG-16 are tested, where the common variant of VGG-16 [Li et al., 2017] for CIFAR-10 is used here. The settings of CCEP are described as follows. It runs for 12 iterations, i.e., T = 12 in Algorithm 1. For the EA (i.e., Algorithm 2) in each group, the population size m is 5, the mutation rates p1 = 0.05 and p2 = 0.1, the ratio bound r is 0.1, the maximum generation G is 10, and 20% of the training set is used for accuracy evaluation. For the final individual selection in line 11 of Algorithm 2, the strategy Sela is used. The setting of finetuning in line 7 of Algorithm 1 is provided in the supplementary material. We run CCEP independently for 10 times with different random seeds.

The comparison results in terms of accuracy drop and pruning ratio of FLOPs are shown in Table 1. For CCEP, we only present the solution with a pruning ratio similar to the comparison methods in Table 1 from the generated archive A. Generally, CCEP not only outperforms state-of-the-art pruning methods which require experts to design good criteria or auxiliary modules, but also automatic EA-based pruning methods. In most cases, CCEP can achieve both larger pruning ratio and smaller accuracy drop. As for the comparison with DeepPruningES, CCEP shows an obvious superiority on accuracy drop with similar pruning ratios. Additionally, we present the curves of pruning process of CCEP during the 10 independent runs in Figure 4. The solid line is the mean value of the 10 runs, and the shadow area represents the 95% confidence interval. The results imply a good stability of CCEP.

4.2 Experiments on ImageNet

ImageNet contains 1.28M images in the training set and 50K in the validation set, for 1K classes. The size of each image is 224×224. ResNet-34 and ResNet-50 are examined. Since ImageNet is much complex than CIFAR-10, a slightly larger mutation rate and pruning ratio bound (i.e., p1 = 0.1 and r = 0.15) are used to improve the pruning speed, and also only 1% of the training set is used for accuracy evaluation. The other settings of CCEP are same as that on CIFAR-10.

The results are shown in Table 2, where the algorithms are sorted by their pruning ratios. For CCEP, we select three solutions, which have pruning ratios similar to that in Table 2, from the final archive A generated in line 12 of Algorithm 1. Generally, CCEP surpasses its counterparts at different levels of pruning ratio with less drop of accuracy. To the best of our knowledge, this is the first time that an EA-based filter pruning method has been examined on ImageNet. The superiority of CCEP on such a large data set provides a more comprehensive demonstration of its effectiveness for neural network pruning. Besides, all the pruned networks (i.e., the archive A in Algorithm 1) generated during the pruning process of CCEP on ResNet-50 are shown in Figure 5. On one hand, CCEP can achieve a set of pruned networks with different pruning ratios in a single run, providing a better flexibility for users. On the other hand, the curve implies the ability of CCEP in finding a good tradeoff between accuracy and pruning ratio. That is, at the beginning, the accuracy of the pruned network can increase as the pruning goes on, implying that the pruned redundant filters might bring noise. In the later stages, the accuracy starts to fall as too many filters are pruned and the representation ability might be damaged.

4.3 Further Studies and Discussion

Figure 6 visualizes the architectures (i.e., the number of filters in each block or layer) of the pruned networks on CIFAR-10, obtained by CCEP. We can observe that on ResNet-56, the filters around the expansion of channels are less pruned than others; while on VGG-16, the filters at the tail part tend to be pruned. These results imply that CCEP can achieve different degrees of redundancy in different layers automatically, which may be difficult to be captured manually.

We have introduced the ratio bound r in mutation to limit the ratio of pruned filters in each iteration of CCEP. Its effect is examined by comparing CCEP with and without r by 5 independent runs for pruning ResNet-56 on CIFAR-10. Figure 7 shows the average accuracy change and pruning ratio of their generated pruned networks. As expected, using r brings significantly better accuracy by preventing overly aggressive pruning, which would make it hard to recover the accuracy.

The influence of hyper-parameters (including the population size m, maximum generation G, mutation rate p1, ratio bound r and final individual selection strategy) of CCEP is examined by pruning ResNet-56 on CIFAR-10, and provided in the supplementary material. Generally, a larger G, or a larger p1 and r would lead to a faster pruning process but at an expense of accuracy. For the final individual selection strategy, Sela achieves better accuracy while Selb shows superiority on efficiency especially on the complex data set. This is intuitive, as a faster pruning process is usually more violent. These results can guide the settings of CCEP to some extent in practice, and the settings used in our experiments are to make a trade-off between the pruning speed and accuracy.

5 Conclusion

This paper proposes an automatic neural network pruning algorithm CCEP. It applies cooperative coevolution to tackle the large search space of neural network pruning, where the layered characteristic of typical neural networks is utilized to tackle the non-trivial separation issue in cooperative coevolution. Experiments show the competitive performance of CCEP, compared with a number of state-of-the-art pruning methods. Besides, the framework of cooperative coevolution makes CCEP highly flexible and easily parallelizable. In the future, we will try to incorporate more advanced EA operators to further improve the performance of CCEP.