Structured Network Pruning by Measuring Filter-wise Interactions

In the pruning scenario, there are two types of filters in each computational module: the redundant and the useful. Taking a CNN with $n$ computational layers as an example, the $l$-th layer is a set of filters $N_{l}=\left\{F_{i}^{l}|i=1,...,c_{out}^{l}\right\}$, where each filter is $F_{i}^{l}\in\mathbb{R}^{C_{in}^{l}\times k^{l}\times k^{l}}$, $c_{out}^{l}$ and $c_{in}^{l}$ are the $l$-layer’s output and input channels, $k^{l}$ is the kernel size. The layer’s pruning sparsity indicates the ratio of number of the redundant filters out of all the filters $N_{l}$ [3]. According to the redundancy criteria and the $l$-th layer’s pruning sparsity, assume $r^{l}$ filters are useful, then the pruning sparsity is $\frac{c_{out}^{l}-r^{l}}{c_{out}^{l}}$. The useful filter set $S_{l}$ of the $l$-th layer is $S_{l}=\left\{F_{i}^{l}|i\in IMP\right\}$, where the $IMP$ is a set of the index of the useful filters identified by their importance according to the specific redundancy criteria. In the inference, each filter consumes a comparable amount of computation but contributes to the output differently. Since the redundant filters’ contributions are much lower than the useful filters, current pruning algorithms believe that the influence of pruning the redundant filter is subtle[19, 41, 3]. However, these approaches neglect the filter-wise interactions’ contributions during the redundancy evaluation.

Since a relatively useless filter might have a considerable collaborative contribution to prediction [25, 40], we need to fairly quantify the impacts of the potential filter-wise interactions on prediction. To achieve this goal, we regard each inference process achieved by $m$ filters in the $l$-th layer as a collaborative game $<M_{l},V>$ [15]. During the inference on a image $I$, each filter is a player and $m$ players align the coalition $M_{l}$ with the contribution $V(M_{l})$, where $m=|M_{l}|\in[1,c_{out}^{l}]$, $V(M_{l})=log\frac{P(\hat{y}=cls|M_{l},I)}{1-P(\hat{y}=cls|M_{l},I)}$ [10] and $\hat{y}$ is the prediction with $M_{l}$. According to the $V(M_{l})$ for each coalition $M_{l}$, we can distribute the contributions on the output when multiple filters interact. In this way, we can quantify each filter’s importance and each layer’s filter utilization strength to identify the functionally loosely-coupled filters. To fairly measure the individual contributions of each filter, we formulate the importance of the $c$-th filter in the $l$-th layer by the Shapley value [37] in Eq.(1).

$$t_{c}^{l}=\left|\sum_{c\in M_{l},M_{l}\subseteq N_{l}}\frac{|M_{l}|!(c_{out}^{l}+1-|M_{l}|)!}{c_{out}^{l}!}\bigtriangleup V(M_{l},c)\right|,$$

(1)

where $\bigtriangleup V(M_{l},c)=V(M_{l})-V(M_{l}-\left\{c\right\})$. When the $c$-th filter forms the $M_{l}$ with other filters in the $l$-th layer, it might positively contribute to the prediction. Considering the potential contribution of each filter, the filter importance $t_{c}^{l}$ assigns the relatively useless filter to a small value. As proven in [2], the $t_{c}^{l}$ is unique and fair to each filter. Therefore, we can fairly discriminate the relative useless filter from the useful filter.

To fairly distribute the contribution of interaction, we first introduce the filter interaction $u_{l}^{d}(i,j)$. The filter interaction is the contribution of the interaction among at least two distinct filters. In this scenario, coalition $M_{l}$ has to consist of $m=d+2$ filters, where $\left\{i,j\right\}\subseteq M_{l}$, $i,j\in[1,c_{out}^{l}]$, $i\neq j$, $d\in[0,c_{out}^{l}-2]$ and $m\in[2,c_{out}^{l}]$. Utilizing the Shapley interaction index [15], the filter interaction $u_{l}^{d}(i,j)$ among $i,j$, when the other $d$ filters exist, define in Eq.(2).

$$u^{d}_{l}(i,j)=\sum_{\left\{i,j\right\}\subseteq M_{l}\subseteq N_{l},\left|M_{l}\right|=d+2}\bigtriangleup V(i,j,M_{l}),$$

(2)

where $\bigtriangleup V(i,j,M_{l})=(V(M_{l})-V(M_{l}-\left\{j\right\}))-(V(M_{l}-\left\{i\right\})-V(M_{l}-\left\{i,j\right\}))$. The larger $u^{d}_{l}(i,j)$, the stronger interaction when $i$,$j$ form a coalition with the other $d$ filters. Notably, it can be proved that $u^{d}_{l}(i,j)$ is unique and fair among all coalitions[37]. With the $u^{d}_{l}(i,j)$, we can measure the filter utilization strength $U_{l}(m)$ of the $l$-th layer in Eq.(3).

$$U_{l}(m)=\frac{\sum_{q=0}^{m-2}\mathbb{E}_{I\in\Omega}\mathbb{E}_{i,j\in N_{l}}[u^{q}_{l}(i,j)]}{\sum_{p=0}^{c_{out}^{l}-2}\mathbb{E}_{I\in\Omega}\mathbb{E}_{i,j\in N_{l}}[u^{p}_{l}(i,j)]},$$

(3)

where the $\Omega$ is the calibration dataset and $|\Omega|=256$ by default. A high value of $U_{l}(m)$ indicates that the interaction strength is intensive when $m$ filters exist. If subtle filters exist, $U_{l}(m)$ achieves a high value with a relatively small $m$. In this way, we can estimate the number of useless filters by $U_{l}(m)$.

In the pruning scenario, the approximation of the optimal pruning plan $S^{*}$ can be time-consuming. Since each layer’s pruning sparsity and the accuracy of the pruned model are non-linearly related, previous studies spend considerable amount of computation to sample the best accuracy achieved by the according pruning sparsity[14, 33, 49]. Based on our redundancy criterion, we can estimate each layer’s sparsity lower bound by the expert experience. Given the desirable filter utilization strength $\theta$ to maintain the basic functionality after pruning, the lower bound of the $l$-th layer’s sparsity $s_{lb}^{l}$ is estimated in Eq.(4).

$$\min_{m}s_{lb}^{l}=\frac{m+2}{c_{out}^{l}}\,s.t.\,U_{l}(m)\geqslant\theta,\,m\in[2,c_{out}^{l}]\land m\in\mathbb{Z}^{+}$$

(4)

According to the $s_{lb}^{l}$ and $t_{c}^{l}$, the relatively useful and important filters always remain in the layer-wise pruning as shown in the dotted box of Figure.2. However, scheduling the layer-wise pruning plan only by the expert experience might compromise with the local optimum [20, 49]. The objective function of the scheduling process is in the E.q.(5).

$$S^{*}=\min_{S}COMP(S)\,s.t.\,ACC(S)\geqslant\alpha,\,S=\left\{s^{l}|l=1,...,n\right\},\,s^{l}\in(0,1.0]$$

(5)

where $COMP(S)$ and $ACC(S)$ are the computation and the accuracy of the pruned model following the pruning plan $S$, and $\alpha$ is the legal validation accuracy for the pruned model. To efficiently approximate the $S^{*}$ through enormous combination of $S$, we integrate $s_{lb}^{l}$ into E.q.(5):

$$S^{*}=\min_{S}COMP(S)\,s.t.\,ACC(S)\geqslant\alpha,\,S=\left\{s^{l}|l=1,...,n\right\},\,s^{l}\in[s_{lb}^{l},1.0]$$

(6)

According to E.q.(5) and E.q.(6), it is straightforward that the searching space sharply shrinks and is feasible for the RL algorithm. Therefore, we integrate our filter-wise interaction-based redundancy criterion into the RL algorithm as shown in Figure 2. In the following, we explain the details of the RL module of the SNPFI.

State $s^{l}$ is defined below for the $l$-th accessible layer:

$$s^{l}=<type,\#param,FLOPs,k^{l},\mu(U_{l}(m)),\sigma(U_{l}(m)),c_{in}^{l},c_{out}^{l}>$$

(7)

The $type$ is the type of the layer, $\#param$ is the number of the parameters, and $FLOPs$ is the number of floating-point operations. The average and the standard deviation of the filter utilization strength, $\mu(U_{l}(m))$ and $\sigma(U_{l}(m))$, are included in the state.

Action $a^{l}$ is the pruning sparsity of the $l$-th layer. In the Agent, the $a^{l}$ is predicted by the policy network $\pi_{\epsilon}$ (the Actor in Figure 2) on the state $s^{l}$ and bounded by the $s_{lb}^{l}$. $a^{l}$ is defined in the Eq.(8).

$$a^{l}=\max(s_{lb}^{l},\pi_{\epsilon}(s^{l}))$$

(8)

where the $\epsilon$ is the trainable parameters of $\pi$. The output range of the policy network is in $(0,1]$.

Reward should convey the future effects on the model’s computational overhead and performance caused by the following layer-wise pruning. Since the $U_{l}(m)$ is naturally related to the number of filters and their cooperative contribution to the inference, we can formulate the reward function $R_{l}(\cdot)$ of the $l$-th layer via $U_{l}(m)$ and $r^{l}$ to alleviate the delayed reward problem [38] in the AMC [20]:

$$R_{l}(r^{l})=\left\{\begin{matrix}\frac{U_{l}(r^{l})}{r^{l}}-\frac{1}{c_{out}^{l}}&,1\leqslant l<n\\ \frac{\sum_{i=1}^{n-1}R_{i}(r^{i})}{n}+\frac{c_{out}^{n}\times U_{n}(r^{n})-r^{n}}{r^{n}\times c_{out}^{n}\times n}&,l=n\wedge ACC(S)\geqslant\alpha\\ \frac{\sum_{i=1}^{n-1}R_{i}(r^{i})}{n}+\frac{c_{out}^{n}\times U_{n}(r^{n})-r^{n}}{r^{n}\times c_{out}^{n}\times n}-n^{2}&,l=n\wedge ACC(S)<\alpha\end{matrix}\right.$$

(9)

where $r^{l}=\lfloor c_{out}^{l}\times a^{l}\rfloor$ is the number of remaining filters and $S=\left\{a^{l}|l=1,...,n\right\}$ is the predicted pruning plan. For CIFAR-10 and MNIST, we evaluate the $ACC(S)$ on the validation set; for ImageNet, we use the training set. When the $S$ ensures the performance of the pruned model, this reward function encourages the $S$ to achieve a higher filter utilization strength with fewer filters during the optimization; When the $S$ violates the legal performance of the pruned model $\alpha$, this reward penalizes the actor for the aggressive pruning sparsity. In this way, the $S\to S^{*}$ step by step.

Policy Update. We utilize the DDPG [32] algorithm to optimize the pruning policy. The parameters of the policy network $\pi$ are updated by the Eq.(10).

$$J(\epsilon)=\mathbb{E}_{s^{l}\sim\rho^{\beta}}[Q^{\pi}(s^{l},\pi_{\epsilon}(s^{l}))]$$

(10)

In DDPG, $\rho^{\beta}$ is the critic network (the Critic in Figure.2) to encourage the right action, $Q^{\pi}$ is the value function to estimate current policy.

During the deployment on the edge device, removing relatively subtle filters with considerable collaborative contribution might be inevitable. The generalization gap between the pruned and the original model emerges in this scenario. Since our redundancy criterion prevents pruning the filters both useful and important, this gap is caused by the distinct interactions of the pruned filters [25, 9]. Therefore, we propose to utilize the filter-wise interaction for fine-tuning as shown in Figure.2. In the perspective of the collaborative game, the remaining $r^{l}$ filters and the entire $c_{out}^{l}$ filters form two different coalitions after pruning on the $l$-th layer: $S_{l}$ and $N_{l}$. If the generalization gap exists, at least one cooperative filter exists in the $\left\{N_{l}-S_{l}\right\}$. To quantify this generalization gap, we define the interaction difference $\Delta I(S_{l},N_{l})$ among $S_{l}$ and $N_{l}$ in the Eq.(11).

$$\Delta I(S_{l},N_{l})=\mathbb{E}_{(S_{l},N_{l})}[\frac{r^{l}}{c_{out}^{l}}\times V(N_{l})-V(S_{l})]$$

(11)

Based on the theorem 1, the non-negative interaction indicates the existence of meaningful interactions that leads to a better generalization. Hence, we propose the ID loss in Eq.(12) to encourage the pruned model to learn these important interactions.

$$L_{ID}=-\frac{1}{n}\sum_{l=1}^{n}\sum_{cls=1}^{\mathbb{C}}P(\hat{y}=cls|\Delta I(S_{l},N_{l}),I)logP(\hat{y}=cls|\Delta I(S_{l},N_{l}),I)$$

(12)

where $L_{ID}$ is the Shannon entropy[39] that uses the $\Delta I(S_{l},N_{l})$ for classification on image $I$, $I$ is sampled from the training set ,$\mathbb{C}$ is the number of the categories and $\hat{y}$ is the prediction based on the $\Delta I(S_{l},N_{l})$. By minimizing the $L_{ID}$, the pruned model can learn the important interaction eventually. Since $\Delta I(S_{l},N_{l})$ is non-negative, $L_{ID}$ can be effective guidance by avoiding the gradient explosion. Therefore, we integrate $\Delta I(S_{l},N_{l})$ with ground truth during the fine-tuning as shown in Figure 2.

Effectiveness of the filter utilization strength. In the ideal, the number of filters has a linear relationship with the accuracy, which indicates that lower sparsity leads to better performance with promise. In reality, the accuracy doesn’t monotonously increase with the proportion of total filters as shown in the shallow or middle layer in AlexNet (Figure 3-left). Thus, assigning all layers with the same sparsity is not effective. Since the accuracy monotonously increases with the filter utilization strength $U_{l}(m)$, a higher $U_{l}(m)$ can ensure better accuracy and is more effective than the sparsity. In this way, our reward function in Eq.(9) can effectively alleviate the delayed reward problem. Meanwhile, the $U_{l}(m)$ converges around $0.5$ in diverse layers and applications as shown in Figure 3-left. Thus, we can estimate the sparsity lower bound $s_{lb}^{l}$ in Eq.(4) with a uniform filter utilization strength $\theta$ for various layers. Since the filter-wise interactions are diverse among layers, the identical value of $U_{l}(m)$ implies different $s_{lb}^{l}$. We utilize this property to boost the optimization of the pruning plan as shown in Eq.(5).

Various interactive mode. As shown in Figure 3-right, a model has three types of interactive modes: low channel first, multi-channel first, and high channel first. As the $U(m)$ of the shallow layer in AlexNet shown, the ‘low channel first’ is the interaction mode when layers’ $U(m)$ reach the inflection point with a few filters; As the $U(m)$ of AlexNet’s the middle layer in AlexNet shown, the ‘multi-channel first’ is the interaction mode that layers’ $U(m)$ distinctly increase multiple times with the growing number of the filters; As the $U(m)$ of the deep layer in MobileNetv1 on the MNIST shown, the ‘high channel first’ is the interaction mode that layers’ $U(m)$ distinctly soar with a high number of channels. Since the interactive mode is diverse in the same model, scheduling aggressive pruning sparsity for a single layer can risk the generalization performance of the whole model. Specifically, even the identical model might behave variously when applied in different scenarios. As shown in Figure 3-right, MobileNetv1 tends to interact in ‘multi-channel first’ in MNIST but shifts from ‘multi-channel first’ to ‘low channel first’ and ends in ‘high channel first’ in CIFAR-10. Hence, our redundancy criterion is vital in real applications to prevent pruning the useful filters.

Effectiveness of the interaction difference. As shown in Figure 4-left, our proposed interaction difference loss $L_{ID}$ is effective in weight recovery for aggressive pruning. Knowledge distillation [22] struggles to converge when the ground truth is intricate for training the pruned model. In contrast, the $L_{ID}$ steadily guides the pruned model to an increasing training accuracy without drastic fluctuation of validation loss. As shown in Figure 4-right, the interaction difference can refine the interactive mode for the pruned model. Before pruning, the ResNet-50 tends to interact in ‘low channel first’ for shallower layers and in ‘multi-channel first’ for deeper layers. After fine-tuning with $L_{ID}$, all layers tend to interact in ‘multi-channel first’ mode, which means filters strongly cooperate and few redundancies exist.

Pruning on CIFAR-10. As shown in Table 1(a), SNPFI reduces more than 60% computation of the MobileNetv1 and ResNet-50 without a significant accuracy drop. In the deployment scenario, our method, nearly $2\times$ faster than the QPNN, can achieve comparable performance with QPNN on the FPGA device without any particular software accelerator [48]. When compressing the highly computational network ResNet-50, SNPFI achieves the highest compression and accuracy among other state-of-the-art methods. Compared with AMC and TAS, SNPFI provides better network architecture by overcoming the delayed reward; When comparing with Greg-2, our method realizes 3.7% more reduction and 2.54% higher accuracy without iterative training to recover the weight; Without empowering the channel selection ability by manual modification of the network, our methods are more applicable and better performance than NS and NPPM.

Pruning on ImageNet. As shown in Table 1(b), SNPFI achieves the best accuracy when pruning generously on ResNet-50. When comparing with Auto-ML methods, SNPFI prunes a 10% of Filters more than the TAS and performs a 2.39% of accuracy higher than the AMC; When comparing with weight-based pruning methods, SNPFI prunes a 10% of channels more than the Greg-2 and LeGR and performs exceeding 2% of accuracy higher than those methods; When comparing with feature-based pruning methods, SNPFI out-performs the SFP and NPPM under comparable pruning ratio. When pruning on MobileNetv1, SNPFI realizes a comparable compression result with the AMC and NS.

RGB model for single-band image. According to Table 2(a) and 2(b), we can experimentally prove that the architectural sparsity varies for the single-band and the multi-band image. On the one hand, different pruning methods can generalize well with less than 45% of the origin when processing single-band images as shown in Table 2(a), which is lower than the empirical value (60% at most [34]).On the other hand, the redundancy does lie at the architecture level when processing single-band images by RGB model. As shown in Table 2(b), applying SNPFI can decline 12% higher of the computation overhead in the ResNet-50 for gray-scale image than the RGB image. The accuracy disparity between the RGB and the gray-scale input might be caused by the absence of colorful information in the gray-scale image, which is vital for object recognition.