Manifold Regularized Dynamic Network Pruning

For a given task, the difficulty of accurately predicting example labels can be various, which thus implies the necessity of investigating models with different capacities for different inputs. Intuitively, a more complex sample with vague semantic information (\eg, images with insignificant objects, mussy background, \etc) may need a more complex network with a strong representation ability to extract the effective information, while a much simpler network lower computational cost could be enough to make the correct prediction for a simpler instance. Actually, this intuition reflects the relationship between instances on a 1-dimensional complexity space, where the different instances are sorted according to their difficulties for the given task. To exploit this property, we firstly measure the complexity of instances and sub-networks, respectively, and then develop an adaptive objective function to align the complexity relationship between instances and that between sub-networks.

Considering that input instances are expected to have correct predictions made by the networks, the task-specific loss (cross-entropy loss) $\mathcal{L}_{ce}({\bm{x}}_{i},\mathcal{W})$ of the networks is adopted to measure the complexity of current input ${\bm{x}}_{i}$. A larger cross-entropy loss implies that the current instance has not been fitted well, which is more complex and needs a network with stronger representation capability for extracting the information. For a sub-network, the sparsity of channel saliency ${\bm{\pi}}^{l}({\bm{x}}_{i})$ determines the number of effective filters in it, and a sparser ${\bm{\pi}}^{l}({\bm{x}}_{i})$ induce a more compact network with lower complexity. Hence, we use the sparsity of channel saliencies as the measurement of network complexity.

Recall that in Eq. (3), the weight coefficient $\lambda$ is vital to determine the strength of sparsity penalty on channel saliencies. However, a same weight coefficient is assigned to all different instances without discrimination. In fact, a simple instance whose cross-entropy loss can be minimized easily may desire a compact sub-network for computational efficiency. On the other hand, those examples that have not been well fitted by the current network yet would need more network capacity to pursue the prediction accuracy, instead of pushing the sparsity further. Thus, the weight of sparsity penalty that controls the network complexity should increase when the cross-entropy loss decreases and vice versa. In an extreme case, no sparsity constraint should be given to the corresponding sub-networks for those under-fitted examples. Specifically, a set of binary learnable variables ${\bm{\beta}}=\{\beta_{i}\}_{i=1}^{N}\in\{0,1\}^{N}$ are used to indicate whether the sub-network for input instance ${\bm{x}}_{i}$ should be thinned out. Thus the optimization objective can be formulated as:

where $\lambda^{\prime}$ is a hyper-parameter shared by all instances to balance the classification accuracy and network sparsity. $\|\cdot\|_{1}$ is the $\ell_{1}$-norm that induces sparsity on channel saliencies and $\mathcal{W}$ is the set of network parameters. $C$ is a pre-defined threshold for instance complexity and the samples with cross-entropy losses larger than $C$ are considered as over complex. Eq. (4) is optimized in a min-max paradigm, \ie, the minimization is applied on parameter $\mathcal{W}$ to train the network, while the maximization on variables ${\bm{\beta}}$ indicates whether the corresponding sub-networks should be made sparse. In practice, ${\bm{\beta}}$ has a closed-form solution. Note that $\|{\bm{\pi}}^{l}({\bm{x}}_{i})\|_{1}\geq 0$ always holds, and the optimal solution of ${\bm{\beta}}$ only depends on the relative magnitude of cross-entropy loss $\mathcal{L}_{ce}({\bm{x}}_{i},\mathcal{W})$ and the complexity threshold $C$, \ie,

Eq (5) indicates that no sparsity is imposed on the corresponding sub-network ($\beta_{i}=0$) if the cross-entropy loss $\mathcal{L}_{ce}({\bm{x}}_{i},\mathcal{W})$ of instance ${\bm{x}}_{i}$ exceeds $C$. In practice, the network is trained in mini-batch, and we empirically use the average cross-entropy loss over the whole dataset in the previous epoch as the threshold $C$. For brevity, the coefficient for the sparsity loss is denoted as $\lambda({\bm{x}}_{i})$, \ie,

The value of $\lambda({\bm{x}}_{i})$ is always in range [0, $\lambda^{\prime}$] and it has a larger value for simpler instances. Then, the max-min optimization problem (Eq. (4)) can be simplified as:

In the training process mentioned above, a negative feedback mechanism [1, 2] naturally exists to dynamically control the instance complexity and network complexity. As shown in Figure 2, when an instance ${\bm{x}}_{i}$ is sent to the network and produces a large cross-entropy loss $\mathcal{L}_{ce}({\bm{x}}_{i},\mathcal{W})$, it is considered as a complex instance and the penalty weight $\lambda({\bm{x}}_{i})$ is reduced to induce a complex sub-network. On account of the powerful representation capability of the complex network, the cross-entropy loss of the same instance $x_{i}$ can be easily minimized, and reduce the relative complexity of the instance. If the dynamic network takes a simple instance as input, the dynamic process is just the opposite. This negative feedback mechanism stabilizes the training process, and finally sub-networks with appropriate model capability for making correct prediction are allocated to the input instances.

Besides mapping instances to the complexity space, the similarity between samples is also an effective clue to customize the networks for different instances. Inspired by the manifold regularization [51, 61], we expect that the instance similarity can be well preserved by their corresponding sub-networks, \ie, if two instances are similar, the allocated sub-networks for them tend to own similar property as well.

The intermediate features $F^{l}({\bm{x}}_{i})$ produced by a deep neural network can be treated as an effective representation of input sample ${\bm{x}}_{i}$. Compared to the original data, ground-truth information is embedded to the intermediate features during training, and hence the intermediate features are more suitable to measure the similarity between different samples. The sub-network for instance ${\bm{x}}_{i}$ can be described by the channel saliencies, which determine the architecture of the network. Note that both the channel saliencies ${\bm{\pi}}^{l}({\bm{x}}_{i})$ and intermediate features $F^{l}({\bm{x}}_{i})$ are corresponding to each layer, and thus we can calculate the similarity matrix of channel saliencies $T^{l}\in\mathbb{R}^{N\times N}$ and similarity matrix of features $R^{l}\in\mathbb{R}^{N\times N}$ layer-by-layer, where the element $T^{l}[i,j]$ ($R^{l}[i,j]$) in the matrix reflect the similarity between saliencies (features) derived from different sample ${\bm{x}}_{i}$ and ${\bm{x}}_{j}$. Suppose that the classical cosine similarity [38] is adopted, $T^{l}$ is calculated as:

where $\|\cdot\|_{2}$ denotes $\ell_{2}$-norm. For intermediate feature $F^{l}({\bm{x}}_{i})\in\mathbb{R}^{c^{l}\times w^{l}\times h^{l}}$ in the $l$-the layer, it is first flattened to a vector using the average pooling operation $p(\cdot)$, and then the similarity matrix is:

Given the similarity matrices $T^{l}$ and $R^{l}$ mentioned above, a loss function $\mathcal{L}_{sim}$ is developed to impose consistency constraint on them, \ie,

where $\mathcal{X}=\{{\bm{x}}_{i}\}_{i=1}^{N}$ and $\mathcal{W}$ denote the input data and network parameters, respectively, and $dis(\cdot,\cdot)$ measures the difference between the two similarity matrices. Here we adopt a simple way that compares the corresponding elements of the two matrices, \ie, $dis(T^{l},R^{l})=\|T^{l}-R^{l}\|_{F}$, where $\|\cdot\|_{F}$ denotes Frobenius norm. In the practical implementation of network training, the similarity matrices are calculated over input data in each mini-batch for efficiency.

Combining the adaptive sparsity loss (Eq. (7)), the final objective function for training the dynamic network is:

where $\gamma$ is a weight coefficient for the consistency loss $\mathcal{L}_{sim}(\mathcal{X},\mathcal{W})$. In Eq. (11), the manifold information is simultaneously excavated from two complementary perspectives, \ie, complexity and similarity. The former imposes the consistency between instances complexity and sub-networks complexity, while the latter induces instances with similar features to select similar sub-networks. Though different perspectives are emphasized, both loss functions describe intrinsic relationships between instances and networks, and can be simultaneously optimized to get an optimal solution.

Based on the channel saliencies of each layer, the dynamic pruning is applied to the given network for different input data separately. Given $N$ different input examples $\{{\bm{x}}_{i}\}_{i=1}^{N}$, the average channel saliencies over different instance are first calculated as $\bar{\bm{\pi}}^{l}=\{\bar{\bm{\pi}}^{l}[1],\bar{\bm{\pi}}^{l}[2],\cdots,\bar{\bm{\pi}}^{l}[c^{l}]\}$, where $c^{l}$ is the number of channels in the $l$-th layer. Then the elements in $\bar{\bm{\pi}}^{l}$ is sorted so that $\bar{\bm{\pi}}^{l}[1]\leq\bar{\bm{\pi}}^{l}[2]\leq\cdots\leq\bar{\bm{\pi}}^{l}[c^{l}]$ and the threshold is set as $\xi^{l}={\bm{\pi}}^{l}[\lceil\eta c^{l}\rceil]$, where $\eta$ is the pre-defined pruning rate and $\lceil\cdot\rceil$ denotes round-off. At inference, only channels with saliencies larger than the threshold $\xi^{l}$ need to be calculated and the redundant features are skipped, which reduces the computation and memory cost. Based on the threshold $\xi^{l}$ derived from the average saliencies $\bar{\bm{\pi}}^{l}$, the actual pruning rate are different for each instances, since the channel saliency ${\bm{\pi}}^{l}({\bm{x}}_{i})$ depends on the input and variant numbers of elements are larger than the threshold $\xi^{l}$. A series of sub-networks with various computational cost are obtained, which are intuitively visualized in Figure 8 of Section 5.3.

The proposed method is compared with state-of-the-art network pruning algorithms on the large-scale ImageNet dataset. The pruning results of ResNet and MobileNetV2 are shown in Table 1 and Table 2, respectively, where the top-1/top-5 errors of the pruned networks and the reduction ratios of FLOPs are reported. For dynamic pruning methods, the average FLOPs of the sub-networks over the whole test dataset are calculated as computational cost.

For ResNet in Table 1, ‘ManiDP-A’ and ‘ManiDP-B’ denote two pruned networks with different pruning rates, respectively. The competing methods include both SOTA static channel pruning method developed recently ([16, 17, 39, 25, 26]) and the pioneering dynamic methods ([9, 6, 20]), indicated by ✗ and ✓ in the table. Our method can reduce substantial computational cost for a given network with negligible performance degradation. For example, the proposed ‘ManiDP-A’ can reduce 46.8% FLOPs ResNet-34 with only 0.01% performance degradation. Compared with the SOTA pruning algorithms, our method obtains pruned networks with less computational cost but lower test errors. The static methods are obviously inferior to ours, \eg, the SOTA method DSA [39] only reduces 40.0% FLOPs and obtain a pruned network with 31.39% top-1 error (ResNet-18), while the proposed ‘ManiDP-A’ can achieve lower test error (31.12%) with more FLOPs reduced (51.0%). Our method also shows superiority to the existing dynamic pruning methods, \eg, FBS [9] achieves 31.83% top-1 error with 49.5% FLOPs pruned, which is worse than our method. We can infer that the proposed ManiDP method can excavate the redundancy of networks adequately to get compact but powerful networks with high performance.

To validate the effectiveness of the proposed ManiDP method on light-weight networks, we further compare it with SOTA methods on the efficient MobileNetV2 [45] designed for resource-limited devices, and the results are shown in Table 2. Our method also achieves a better trade-off between network accuracy and computational cost than the existing methods. For examples, the proposed ‘ManiDP-A’ reduces 37.2% FLOPs of MobileNetV2 with only 0.38% accuracy loss, while the pruned network obtained by the competing method FBS [9] sacrifices 0.87% accuracy for pruning 33.6% FLOPs. The results show that even light-weight networks are over parameterized when exploring redundancy for each instances separately, which can be further accelerated by the proposed method and deployed on edge devices.

The realistic accelerations of the pruned Networks on ImageNet are shown in Table 3, which is calculated by counting the average inference time for handling each image on CPUs. The realistic acceleration is slightly less than the theoretical acceleration calculated by FLOPs, which is due to practical factors such as I/O operations (\eg, accessing weights of networks), BLAS libraries and buffer switch, whose impact can be further reduced by practical engineering optimization.

On the benchmark CIFAR-10 dataset, the comparison between the proposed ManiDP and SOTA channel pruning methods are shown in Table 4. Compared with SOTA methods, a significantly higher FLOPs reduction is achieved by our method with less degradation of performance. For example, using our method, more than 60% FLOPs of the ResNet-56 model are reduced while the test error can still achieve 6.36% using ManiDP. Compared to the static methods (\eg, HRank [28] with 6.83% error and 50.0% FLOPs reduction) and dynamic method (\eg, FBS [9] with 6.48% error and 53.6% FLOPs reduction), our method shows notable superiority.

Effectiveness of Manifold Information. To maximally excavate network redundancy corresponding to each instance, the manifold information between instances is explored from two perspectives, \ie, complexity and similarity. The impacts of whether exploiting complexity or similarity relationship is empirically investigated in Table 5, indicated by ✓ and ✗. The classification error and the performance gap compared to the base models are reported. Without utilizing the complexity relationship means fixing the trade-off coefficient $\lambda({\bm{x}}_{i})$ between lasso loss and cross-entropy loss, which obviously increases the error incurred by pruning (\eg, 1.43% \vs0.94% on ImageNet). The unsatisfactory performance is due to the improper alignment, \ie, cumbersome sub-networks may be assigned to simple examples, while complex instances are handled by tiny sub-networks with limited representation capability. For the similarity relationship, deactivating it (setting coefficient $\gamma$ for similarity loss to zero) incurs larger performance degradation (\eg, 1.43% \vs0.98%), which validates the effectiveness of exploring the similarity between features of instances and the corrsponding sub-networks. Thus, exploiting both the two perspectives of manifold information is necessary to achieve negligible performance degradation (\ie, only 0.57% error increase on ImageNet).

Weight coefficients $\lambda^{\prime}$ and $\gamma$. The weights of sparsity loss and similarity loss are controlled by coefficients $\lambda^{\prime}$ (Eq. (4)) and $\gamma$ (Eq. 11), whose impact on the final test accuracies is shown in Figure 3. A larger $\lambda^{\prime}$ induces more sparsity on channel saliencies, which will have less impact on the network outputs when discarding channels with small saliencies. On the other hand, the sparsity will affect the representation ability of networks and incur accuracy drop (Figure 3 (a)). Analogous phenomenon exists when varying coefficient $\gamma$ for similarity loss. The test accuracy of the pruned network is improved when increasing $\gamma$ unless it is set to an extremely large value, as the similarity between different instances is excavated more adequately. Note that our method is robust to both hyper-parameters and works well in a wide range (\eg, range [0.001,0.01] for $\lambda$ and values around 10.0 for $\gamma$), empirically.

Memory/FLOPs and accuracies \wrtPruning Rate. The impact of different pruning rate is shown in Figure 4. When a single instance is sent to the network, the memory cost for accessing network weights can be reduced as ineffective weights do not participate the inference process. With a large reduction of computational cost and memory, the pruned network can still achieve a high performance. For example, when setting the pruning rare to 0.6% with 73.87% FlOPs and 67.42% memory reduction, the pruned ResNet-56 can still achieve an accuracy of 93.29% (only 0.41% accuracy drop compared to the original network).

Visualization. Different sub-networks with various computational costs (\ie, FLOPs) are generated for each instance by pruning different channels. Using ResNet-34 as the backbone, the FLOPs distribution of different sub-networks over the validation set of ImageNet are shown in Figure 8, where $x$-axis denotes FLOPs and the $y$-axis is the number of sub-networks. The FLOPs of sub-networks varies in a certain range \wrtthe complexity of instances. Most of the sub-networks own medium sizes and a small quantity of sub-networks activate more/less channels to handle harder/simpler instances. Some representative images handled by the corresponding sub-networks are also shown in the figure. Intuitively, a simple example (\eg, ‘bird’ and ‘dog’ in the red frames) that can be correctly predicted by a compact network usually contains clear targets, while images with obscure semantic information (\eg, too large ‘orange’ and too small ‘flower’ in the blue frames) require larger networks with more powerful representation ability. More visualization results are shown in the supplementary material.

In the training procedure, the coefficient $\lambda({\bm{x}}_{i})$ (Eq. (6) of the main paper) controls the weight of sparsity loss according to the complexity of each instance. Recall that $\lambda({\bm{x}}_{i})=\lambda^{\prime}\cdot\beta_{i}\frac{C-\mathcal{L}_{ce}({\bm{x}}_{i},\mathcal{W})}{C}\in[0,\lambda^{\prime}]$ , where $\lambda^{\prime}$ is a fixed hyper-parameter for all instances. Using ResNet-56 as the backbone, the variable parts $\lambda({\bm{x}}_{i})/\lambda^{\prime}\in[0,1]$ for complex/simple examples in CIFAR-10 are shown in Figure 6. $\lambda({\bm{x}}_{i})/\lambda^{\prime}$ keeps small for complex examples (\eg, the vague ‘ship’ in (a)) and then less channels of the pre-defined networks are pruned for keeping their representation capabilities. When sending simple examples (\eg, clear ‘airplane’ in (b)) to the dynamic network, $\lambda({\bm{x}}_{i})/\lambda^{\prime}$ keeps large in most of the epochs, and thus the corresponding sub-network becomes sparser continuously as the numbers of iteration increases. Note that $\lambda({\bm{x}}_{i})/\lambda^{\prime}$ changes dynamically in the training process. For example, the sparsity weight automatically decreases in the last few epochs as the corresponding sub-network is compact enough and should pay more attention to accuracy (Figure 6 (b)), which ensures that the models can fit input instances well.

The similarity matrices $R^{l}$ for intermediate features and $T^{l}$ for channel saliencies are shown in Figure 7, where different colors denote the degree of similarity (\ie, a yellower point means higher degree of similarity between two instances). The ResNet-56 model trained with/without the similarity loss $\mathcal{L}_{sim}$ (Eq. (10) in the main paper) is used to generate features and channel saliencies for calculating the similarity between instances randomly sampled from CIFAR-10. When training dynamic network without similarity loss $\mathcal{L}_{sim}$, the similarity calculated by features and that by channel saliencies are very different (Figure 7 (a), (b)). When using similarity loss (Figure 7 (c), (d)), the similarity matrices $R^{l}$ and $T^{l}$ are more analogous as the similarity loss penalizes the inconsistency between similarity matrices to align the similarity relationship in the two spaces.

We sample representative images with different complexity from ImageNet and intuitively show them in Figure 8. From top to bottom, the computational costs of sub-networks used to predict labels continue to increase. Intuitively, simple instances that can be accurately predicted by compacted networks usually contain clear targets, while the semantic information in complex images are vague and thus requires larger networks with powerful representation capability.