Title: SPARSE-COMPLEMENTARY CONVOLUTION FOR EFFICIENT MODEL UTILIZATION ON CNNS Anonymous

Abstract: We introduce an efficient way to increase the accuracy of convolution neural networks (CNNs) based on high model utilization without increasing any computational complexity. The proposed sparse-complementary convolution replaces regular convolution with sparse and complementary shapes of kernels, covering the same receptive field. By the nature of deep learning, high model utilization of a CNN can be achieved with more simpler kernels rather than fewer complex kernels. This simple but insightful model reuses of recent network architectures, ResNet and DenseNet, can provide better accuracy for most classification tasks (CIFAR-10/100 and ImageNet) compared to their baseline models. By simply replacing the convolution of a CNN with our sparse-complementary convolution, at the same FLOPs and parameters, we can improve top-1 accuracy on ImageNet by 0.33% and 0.18% for ResNet-101 and ResNet-152, respectively. A similar accuracy improvement could be gained by increasing the number of layers in those networks by ∼ 1.5×.

1. INTRODUCTION:

Object recognition has achieved significant improvement through convolutional neural networks (CNNs), e.g., ResNet (He et al. (2016a) ) and DenseNet (Huang et al. (2017) ). In order to achieve competitive performance on large-scale datasets such as ImageNet (Russakovsky et al. (2015) ), these networks usually require increasing model capacity substantially with a deeper network, e.g. ResNet-200, or a wider network, e.g. DenseNet-161. Nonetheless, it seems pretty obvious that the redundancy in those models are still high (Mao et al. (2017) ).

This observation encouraged us to investigate an efficient way to increase model utilization1 for complex architectures. It has been demonstrated that there are multiple ways to increase model utilization, e.g., by keeping the same performance while reducing resource usage (Wen et al. (2017) ; Kim et al. (2016) ; Ioannou et al. (2016) ) or increasing the accuracy with the same resource usage.

There are two major approaches to increase mode utilization from a macro-architecture2 of a network perspective. ResNet adds the residual shortcut to assure that the loss at the end can be propagated to all parameters smoothly; thus, all parameters are treated equally for better utilization. DenseNet reuses the extracted features intensively from different layers to save the computations and parameters while achieving good performance. However, both these approaches still rely on regular convolution in their micro-architectures. We found out that deeper and/or wider macroarchitectures naturally introduce more redundancy on convolutional layers; the types of convolution can be optimized for such macro-architectures.

We propose a pair of deterministic sparse-complementary convolutional kernels in either the spatialwise or channel-wise domain to reduce the complexity of each kernel; each sparse kernel has a complementary kernel to approximate the receptive field of regular kernels. Since a sparse kernel saves the floating-point operations (FLOPs) and parameters for a convolution, we are able to enrich Zhou et al. (2016) ; Alvarez & Salzmann (2016) ; Mao et al. (2017) ; Liu et al. (2017) ; Wen et al. (2017) Random but structural sparsity Y Denton et al. (2014) ; Jaderberg et al. (2014) ; Zhang et al. (2015) ; Kim et al. (2016) Low-rank approximated kernels Y Mamalet & Garcia (2012) ; Szegedy et al. (2016) ; Sun et al. (2016) Deterministic low-rank kernels N Ioannou et al. (2016) ; Iandola et al. (2016) ; Ioannou et al. (2017) Mixed-shape kernels Y Ours, sparse-complementary kernels Mixed-shape kernels and deterministic sparsity - * : Orthogonality denotes whether or not their works conflict with ours. feature representation by adding either layers or kernels; therefore our models achieve better model utilization and accuracy under the same resource budget.

The contributions of this paper include the following:

1. We achieve better model utilization on all models with the ResNet and DenseNet macroarchitectures on CIFAR-10/100 and ImageNet. We gain 0.33% and 0.18% for ResNet-101 and ResNet-152 on ImageNet, respectively, without increasing any FLOPs and parameters. Such gain would have required adding 1.5× more layers to those networks. Notice that ResNet-152 only improves 0.44% top-1 accuracy than ResNet-101. 2. We propose a better micro-architecture for CNNs. The proposed sparse-complementary kernels save computations and parameters due to their sparsity. The complementary property of a kernel compensates for receptive field missed from the other sparse kernel. 3. We enrich the feature representation under identical resource budget thanks to the sparse and complementary properties in the kernels. 4. We prove that the proposed sparse-complementary convolution achieves the expected speed on the current NVIDIA GPU.

2. RELATED WORK:

To increase model utilization, several approaches have been proposed that reduce the model parameters and computations with comparative performance; however, our proposed method consists of improving performance with the same model parameters and computations. Table 1 highlights the distinct features of our work, compared to previous research approaches in this space.

Random Kernel Sparsity remove unimportant weights based on a trained model. In general, this approach imposes different weight regularization to increase parameter utilization. Some of the research work in this area enforces the zeros into a certain shape, such as forcing all zeros to locate in the same kernel or the same channel within a kernel (Wen et al. (2016) 2014)). Typically, this approach needs a pre-trained model; re-training is then required to recover performance after pruning weights; however, some of them can directly train from scratch by chaning the regularizer in the objective function. Nonetheless, the random sparsity might provide limited advantages on reduction of model size and computations, e.g. the indexed table for non-zero weights or efficient computations in sparse kernels are challenges in terms of implementation overhead. Even though some of works use random but structural sparsity and gain the speed up over CPU or GPU; however, due to the random structure, it still limits its advantages when deploying on customized neural network accelerator, which might be implemented by ASIC and FPGA. Conversely, thanks to the deterministic and complementary characteristics of our sparse convolution, we can easily achieve competitive speed even with the current CUDNN 6.0. Furthermore, since our method is orthogonal to those approaches, we can integrate them into our solution to increase model utilization.

EQUATION

Low-rank Approximated Kernels deploy the factorization on learned kernels into low-rank kernels, or directly deploys hand-crafted low-rank kernels. Tensor factorization can be done by decomposing the kernels in a pre-trained model into multiple low-rank kernels by high-order tensor approximation (Denton et al. (2014) ; Kim et al. ( 2016)), singular value decomposition (Liu et al. (2015) ), data-driven low-rank approximation (Jaderberg et al. (2014) ), or non-linear approximation (Zhang et al. (2015) ). By lowering the rank of weight tensors, the redundancy within/between weight tensors can be removed to make the model more compact for higher model utilization. On the other hand, (Mamalet & Garcia (2012) ; Szegedy et al. (2016) ; Sun et al. (2016) ; Fan et al. (2017) ) deploy hand-crafted low-rank kernels to approximate high-rank kernels, but the information lost in the low-rank kernels may be unrecoverable. Figure 1 (b) shows an example that sequentially uses low-rank kernels at consecutive layers as full-rank kernels. Our approach uses complementary kernels to compensate the missed information from another sparse kernel pair. Furthermore, since our approach is orthogonal to the factorization approach, our proposed kernels can be factorized into lower-rank kernels to increase model utilization.

Mixed-shape Kernels utilize multiple shapes kernels in a convolutional layer (Ioannou et al. (2016) ; Iandola et al. ( 2016)) as shown in Fig. 1 (c ). Ioannou et al. (2016) uses two 1-D kernels and one optional 2-D kernel, and then combines the extracted features via a 1×1 convolution. The 1×1 convolutional layer plays an important role to compensate the disadvantage of using non-complementary kernels. In contrast, our approach replaces their 1 × 3 and 3 × 1 kernels with sparse-complementary kernels to enrich the feature representations of a network; the complementary characteristic of our networks do not need an additional 1 × 1 convolutional layer, which is not optimized on current GPUs.

3. PROPOSED SPARSE-COMPLIMENTARY CONVOLUTIONAL KERNEL:

The current design of a convolutional kernel in a CNN is inefficient in utilizing parameters of micro-architectures, which results in unnecessary computations and parameters. Several works had demonstrated that, e.g., the model of a CNN can be easily pruned (Han et al. (2015) ; Mao et al. (2017) ; Molchanov et al. (2017) ) or factorized but keep comparative accuracy (Zhang et al. (2015) ; Kim et al. (2016) ) regardless of its macro-architecture, including, VGGNet, ResNet and DenseNet. Therefore, we became interested in designing CNN micro-architecture that uses the right amount of parameters while sustaining the same accuracy under the same computations. We present a sparsecomplementary convolution kernel which can improve accuracy while keeping a similar number of computations and parameters. By simplifying each convolutional kernel with deterministic sparse pattern which uses almost half of parameters of regular kernels, we use saved parameters and FLOPs to add either more convolutional kernels (wider network) or convolutional layers (deeper network) to enrich feature representation; in addition to it, the hardware-friendly deterministic sparsity allows us to achieve almost theoretical speed-up on GPU with CUDNN 6.0. In this paper, two types of sparse kernels are proposed, spatial-wise sparse-complementary (SW-SC) kernel and channel-wise sparse-complementary (CW-SC) kernels, to achieve accuracy improvement under the same resource for the most recent network architectures, ResNet and DenseNet.

In following sections, we explain the sparse-complementary kernels and discuss its advantages with respect to their receptive field coverage; and then, we discuss how we use the saved resource in computations and parameters to improve accuracy compared to its baseline.

3.1. SPARSE-COMPLEMENTARY KERNEL DESIGN:

We introduce two types of sparse-complementary kernels in this chapter, such as spatial-wise and channel-wise sparse-complementary kernels. The sparse kernel is designed to extract the feature efficiently and its complementary pattern assures the sparse convolution has no missed regions in receptive field across layers. The two complementary sparse kernels are always paired in one convolutional layer. Let W represents the weights of a regular k × k convolutional layer with C channels and N kernels; thus W is a 4-D tensor, and W(x, y, c, n) denotes the weight of the n-th kernels at the c-th channel and spatially located at (x, y) locations, where x and y range from 0 to k -1, where k is kernel size.

The spatial-wise sparse-complementary (SW-SC) convolutional kernel sparsifies the kernel in the spatial domain. Figure 2 (a) and (b) show an example of SW-SC kernels for 3×3 convolution. Those kernels are either even-and odd-indexed in the spatial domain for all channels in a kernel except for the center point 3 . When kernel size is 3 × 3, the kernel shape becomes +-shape (W sw,even ) or ×-shape (W sw,odd ). If we formulate the kernel with regular kernel coordinate, the locations with zero weights are (for a convolutional layer with N kernels):

W sw,even (x, y, c, 2m) = 0, if (y × k + x) mod 2 = 1 and (y = k/2 and x = k/2 ), W sw,odd (x, y, c, 2m + 1) = 0, if (y × k + x) mod 2 = 0 (1)

where m < N 2 , and other non-zero locations are trainable weights. Figure 2 (a) and (b) show the kernels in both 3D and 2D views for 3 × 3 SW-SC kernels.

On the other hand, with the similar idea, the channel-wise sparse-complementary (CW-SC) convolutional kernel sparsifies the kernel in channel domain, and a pair of kernels are complemented to each other. Thus, one of kernels would take even-indexed feature maps as an input for convolution and the other kernel would use odd-indexed feature maps. The locations of zero weights can be equivalently represented as (for a convolutional layer with N kernels):

W cw,even (x, y, c, 2m) = 0, if c mod 2 = 1, W cw,odd (x, y, c, 2m + 1) = 0, if c mod 2 = 0 (2)

where m < N 2 , and other non-zero locations are trainable weights. Figure 2 (c) shows an example for k×k CW-SC kernels. The major difference between CW-SC and group convolution (Krizhevsky et al. (2012) is the order of output feature maps. Thus, if two CW-SC layers are deployed consecutively, it is different from deploying two consecutive group convolutions. E.g., for CW-SC, every feature map at layer L+2 gets the information of all feature maps at layer L; however, for the group convolution, the feature map at layer L+2 only gets the information from either the first half or the second half feature maps at layer L. In short, we can consider CW-SC embeds channel reordering on the output feature maps.

3.1.1. RECEPTIVE FIELD OF PROPOSED KERNELS:

The proposed complementary kernels are designed to cover the identical receptive field that regular kernels can cover when they are applied across several layers. Take stacking multiple 3 × 3 convolutional layers as an example, Fig. 3 compares the effective receptive field for different types of 3 The kernels in a pair are spatially complemented to each other on all positions except for the center point. c)). We discuss the effective receptive field of a location (across multiple channels) at Layer L from two previous layers (Layer L -1 and L -2). Figure . 3 (a) is the regular one, stacking conventional layers, and its effective receptive field is the intact one, i.e. covering everything as expected.

Nonetheless, if we sequentially apply sparse kernels (even-indexed (W sw,even ) and odd-indexed (W sw,odd )), like in Fig. 1 (b) (Fan et al. (2017) ), the effective receptive field is narrow than the conventional one. Figure 3 (b) and (c) show the results for applying W sw,even and W sw,odd in different orders. Moreover, if we do not apply sparse and complementary kernel alternatively, more receptive fields are uncovered.

For the case of SW-SC or CW-SC kernels, we can achieve the same receptive field since the convolution operates across input channels. That is, the feature maps at layer L -1 is derived from both odd-indexed (×-shape for 3 × 3 kernel) kernels and even-indexed (+-shape for 3 × 3 kernel) kernels at layer L -2. Then, when applying one of sparse and complementary kernels on feature maps of the L -1-th layer, the produced features are able to contain whole receptive field from layer L-2. Figure 3 (d) and (e) (corresponding to (b) and (c)) show the receptive field of applying SW-SC kernels. Thanks to the complementary characteristic, most uncovered receptive fields are recovered (the yellow blocks in Fig. 3 .) Therefore, it again justifies the advantages of complementary feature in designing kernels. The effective receptive field of CW-SC can be derived in a similar approach.

The experimental results show that utilizing complementary patterns within the same layer is better than applying single pattern within one layer (see Section 4.1.4).

3.2. ENRICHING FEATURE REPRESENTATION UNDER IDENTICAL COMPUTATIONAL BUDGET:

Enforcing deterministic sparsity in either spatial or channel domain enables us to utilize the saved resource budget in both computations and parameters for enriching feature representations in advance. The straightforward idea is either to increase the number of layers or the number of kernels in a layer. He & Sun (2015) compared the performance of wider or deeper network; however, their conclusions show that deeper network is better than the wider network for most cases, but at certain depth level, the deeper network performed worse than the shallow network. This is because they did not test on the ResNet architectures, the deeper network might have suffered from gradient vanishing problem. On the other hand, WideResNet (Zagoruyko & Komodakis (2016) ) discussed the advantages of increasing the number of kernels in a convolutional layer with respect to accuracy and computational efficiency; furthermore, current NVIDIA GPU is more computational-friendly for parallelism from multiple kernels within a layer rather than multiple layers with a small number of kernels. Under similar computational load, the wider networks are always more efficient than deeper networks for NVIDIA GPU. Details are discussed in Section 4.1.3. Based on these observations, we favor increasing the number of kernels in a convolutional layer rather than to increase the depth of network. Increasing the number of kernels in a layer also potentially increase the capability of feature expressivity of the network due to the fact that each convolutional kernel can combine more input feature maps from the previous layers to represent more complex features4 . Whereas, if we use deeper networks, each layer might be trapped into a bad feature representation due to the limitation of sparse kernels. The empirical experiments we performed show that, in most of the cases, both wider and deeper networks were able to achieve better classification accuracy than baseline, and the wider networks are the best in accuracy (see Section 4.1.3).

To increase the number of kernels in a layer, we use a control parameter w for all layers in a network, i.e., the increasing ratio is homogeneous across the whole network. Take ResNet-18 for ImageNet as an example (He et al. (2016a) ), the original number of parameters and FLOPs per pixel of a residual block is (a residual block contains two 3 × 3 convolutional layers in ResNet-18):

EQUATION

)

where C is the number of input feature maps and also the number of kernels in the convolutional layers for simplicity.

For our SW-SC convolutional layer, with the control parameter, w, the number of parameters and FLOPs per pixel would be:

EQUATION

where 5 comes from five active weights in a 3 × 3 kernel, and the number of input feature maps and the number of kernels in a convolutional layer become Cw when we increase the number kernels in a layer. Thus, under the constraint of comparative resource budget, we set w to 1.3125 in this case.

4. EXPERIMENTAL RESULTS:

To evaluate the proposed spatial-wise and channel-wise sparse-complementary (SW-SC and CW-SC) convolutional kernels, we applied them onto on state-of-the-art network architectures for the image classification task, including ResNet (He et al. (2016a; b) ) and DenseNet (Huang et al. (2017) ) for the CIFAR-10/100 (Krizhevsky & Hinton (2009) ) and ImageNet-1K (Russakovsky et al. (2015) ) datasets. For all experiments, we replace all 3 × 3 and 1 × 1 kernels by SW-SC and CW-SC convolutional kernels, respectively. We add a suffix -sc to refer to our models with either SW-SC, CW-SC, or both SW-SC and CW-SC for both deeper and wider networks, and we apply the same increasing ratio (w) for number of kernels for all convolutional layers in a CNN. The setting of w is varied for different networks because w is derived to match the resource usage to baselines (as the example in Section 3.2). For ResNet, w is applied for all convolutional layers in residual blocks and the first 7 × 7 convolution for the ImageNet dataset; for DenseNet, w is directly applied on the growth rate, which is the increasing ratio of channels for each layer. All experiments are completed by Tensorpack (Wu ( 2017)), a high-level API for Tensorflow (Abadi et al. (2015) ).

4.1. EVALUATION ON CIFAR-10/CIFAR-100:

For the CIFAR-10/CIFAR-100 datasets, we evaluate three perspectives, including (I) classification accuracy, (II) accuracy and effective FLOPs of our deeper and wider networks and (III) the advantages of having complementary kernels in the same layers.

4.1.1. NETWORKS AND TRAINING DETAILS:

We use pre-activation ResNet for CIFAR-10/100 (He et al. (2016b) ), and we train all ResNets based on the setting of original work, i.e., data augmentation includes standard translation augmentation and random flipping in horizontal direction, image standardization is applied, and weights are initialized based on the method in He et al. (2015) ; however, we use whole 50k training images for training rather than splitting training data into 45k and 5k images as the original work did. We trained 185 epochs for ResNets with batch size 128, and the momentum is 0.9 and the weight decay is 0.0001; learning rate is set to 0.01 in the beginning for warm up and then changes to 0.1 after the first epoch; then, the learning rate is dropped 10 times at 91 and 137 epochs. For DenseNet, we adopt bottleneck and compression setting in DenseNet (Huang et al. (2017) ) and the training setting of original paper. Most settings are identical to ResNet with following exceptions, including the trained epochs, batch size and learning rate. The trained epochs are 300 with batch size 64, and the initial learning rate is 0.1 without warming up and is reduced by 10 times at 150 and 225 epochs.

4.1.2 CLASSIFICATION ACCURACY ON CIFAR-10/100

Figure 4 compares baselines and our deeper and wider networks for all ResNets. We apply only SW-SC on ResNets since only 3 × 3 convolutional layer in the network. Our wider networks (ResNet-scwider) consistently surpass the baselines by ∼0.5% and ∼1% accuracy improvement on the CIFAR-10 and CIFAR-100 datasets across different depths of the ResNet networks, respectively, without introducing any complexity. Thus, under identical FLOPs and parameters, our models can utilize the models more efficient than the baselines, which indicates that having more simpler kernels can achieve better accuracy (See Table 8 in the supplementary section for details.). Furthermore, for both CIFAR-10 and CIFAR-100, our wider ResNet-110-sc (w = 1.3125) achieves better performance than ResNet-164, which increases 1.5× more layers as compared to ResNet-110. Thus, it again justifies the proposed sparse-complementary kernels can achieve better model utilization. On the other hand, for DenseNet, we apply both SW-SC and CW-SC on 3×3 and 1×1 convolutional layers respectively and the results are shown in 2. For CIFAR-10, we see minor performance degradation but we observe large improvement on CIFAR-100 dataset (0.74%); thus, our model is still better than the baseline in DenseNet architecture since CIFAR-100 is a more difficult dataset in comparison with CIFAR-10. The values larger than 1 mean wider networks achieve higher effective FLOPs.

network configuration can be more efficient than the deeper network. Since by having more convolutional kernels, we also extend the dimension of feature maps for exploring better feature representation at each layer rather than searching better feature representation at deeper layers.

On the other hand, as we discussed in section 3.2, for NVIDIA GPU, the wider networks achieved effective FLOPs than the deeper networks. Table 3 shows the ratio of effective FLOPs between wider and deeper SW-SC ResNet at the same FLOPs, and no matter the depth of base networks, the wider ones are always efficient than the deeper networks. This is because current GPU is Single-Instruction-Multiple-Thread (SIMT) architecture, which is more suitable for computing the same instruction concurrently. That is, GPU can exploit higher parallelism when executing more identical instructions. Hence, if we have more kernels in the same convolutional layer, GPU can potentially dispatch all kernels onto GPU's cores to achieve better hardware utilization for faster speed.

4.1.4. ANALYSIS ON SPARSE-COMPLEMENTARY KERNEL:

Table 4 shows the advantages in having complementary kernels at one convolutional layer rather than separating them into consecutive layers (Fan et al. (2017) ). Sparse-complementary convolution helps the next layer mixing the information from both phases to provide better feature representation (larger receptive field as shown in Fig. 3 ). We found out that applying complementary kernels in the same layer can provide a better growth rate of receptive field, i.e., given the same number of layers, the receptive field with our approach can be larger. So, we achieve higher improvement on shallower networks, like ResNet-32 and ResNet-110; however, for ResNet-164, the deeper networks might compensate insufficient receptive field by its depth, both configurations achieve comparative results.

4.2. EVALUATION ON IMAGENET:

We also apply our SW-SC and CW-SC kernels on ResNet and DenseNet for the ImageNet dataset, and our networks consistently achieve better accuracy under similar FLOPs and parameters.

We use normal ResNet5 (He et al. (2016a) ) for the experiments on the ImageNet dataset since we found out that the normal ResNet achieves better accuracy than pre-activation ResNet on ImageNet, and we would like to evaluate performance improvement on top of higher accuracy model by our method. We train ResNet based on original work but with a minor modification: inside a residual block, the γ parameter in the last batch normalization layer is initialized to zero (Goyal et al. (2017) ), which lets the information flows fro identity shortcut in the beginning. We also apply color, scale and shift augmentation for training data (Wu (2017) ; Gross & Wilber (2016) ; Szegedy et al. (2015) ). For both ResNet and DenseNet, we initialize weights based on the method in He et al. (2015) and train 110 epochs with total batch size 256. The momentum is 0.9 and the weight decay is 0.0001; initial learning rate starts is 0.1 and then it is dropped 10 times at 30, 60, 85, 95 and 105 epoch.

4.2.2. CLASSIFICATION ACCURACY ON IMAGENET:

Figure 5 compares baselines and our models. To evaluate the trained model, we resize the shorter side of an image to 256 with the same aspect ratio, and then crop center region, 224 × 224, to evaluate top-1 error rate. For ResNet-18 and ResNet-34, we only apply SW-SC kernels since the residual block is composed of two 3 × 3 convolutional layers; for other ResNets and DenseNet, both SW-SC and CW-SC kernels are applied. Again, we achieve significant improvement on ResNet-18 and ResNet-34 when applying our proposed kernels with w = 1.3125: more than 1% top-1 accuracy as compared to baselines. On the other hand, for ResNet-50, ResNet-101, ResNet-152 and DenseNet-121, those are high accuracy deep CNNs, it is difficult to improve their performance by simply modifying their micro-architectures. E.g., ResNet-152 outperforms ResNet-101 only 0.44% top-1 accuracy, but ResNet-152 increase 1.5× more layers, which is about 1.5× FLOPs and parameters, to ResNet-101. Our models can consistently provide better top-1 accuracy, and our ResNet-101-sc improves 0.33% top-1 accuracy, which boosts its performance close to ResNet-152 without introducing any overhead on FLOPs and parameters as compared to original ResNet-101; and our ResNet-152-sc provides another ∼ 0.2% improvement (See Table 10 in the supplementary section for details .). Table 2 shows the same trend on DenseNet-121; without bringing any overhead, our model gains 0.3% top-1 accuracy.

4.3. BENCHMARK OF SPARSE-COMPLEMENTARY CONVOLUTION ON NVIDIA GPU:

In order to practice our SW-SC convolution on NVIDIA GPU with CUDNN, which is optimized for current state-of-the-art networks and convolutional kernels, we implemented our convolutions and archived competitive speed under the same computational load. All baselines' performance measurement relied on CUDNN 6.0. Thanks to the deterministic sparsity, we can easily revise original im2col routine to lower an input tensor into a matrix efficiently and then also exploit efficient matrix multiplication on GPU. We use NVIDIA K80 and Caffe framework (Jia et al. (2014) ) for our speed benchmark. Table 5 compares the speedup ratio over the baselines under identical FLOPs; the sparse-complementary kernels achieve competitive speed against to highly-optimized CUDNN (Lavin & Gray (2016) ).

4.4. DISCUSSION ON PERFORMANCE BOOST WITH SIMPLE KERNELS:

In this chapter, we would like to address the possibility of performance increase with other types of simple kernels. Our proposal which increases accuracy based on the increased number of kernels relies on computation savings from its simpler convolution compared to 3 × 3 regular convolution. It means that 1 × 3, 3 × 1 kernels (Ioannou et al. (2016) ) would have more chances to increase the number of kernels for boosting the accuracy consequently. In our additional experiments, as pected, these kernels showed the similar performance gain as well, since those kernels also have full receptive coverage of regular convolution like our complementary kernels. However, in this paper, we focused on the effects sparse-complementary kernel for some reasons 6 , therefore, comparing benefits of different shapes of kernels is not part of purpose of this paper. But it seem clear that our performance boost proposal can be applicable for other types of simpler kernels, including 1 × 3, 3 × 1 and mixed-shape kernels, eventually.

4.5. COMPARISON WITH OTHER WORKS:

To validate our kernel design, we compared our work with Ioannou et al. (2016) , which uses 1 × k, k × 1, and 1 × 1 convolutions to replace 3 × 3 convolutions. We use ResNet-50 as the case study (we trained the networks by ourselves), and the results are shown in Table 6 . Under bottleneck residual block used in ResNet-50, the features are embedded into low-dimension space before applying non 1 × 1 convolutions; thus, 1 × 3 and 3 × 1 convolutions are not enough to approximate original 3 × 3 for better performance in low-dimension space. Even with wider network setting, the performance is worse than baseline. (Note that 1 × 3 and 3 × 1 are rank-1 kernels and they are not complemented.). On the other hand, our SW-SC kernels are rank-2 (+-shape) and rank-3 (×-shape), which provide 6 One of the reason is the complementary × and + kernels are more suitable for computer vision task by nature. We are investigating its potential for different tasks such as localization, segmentation, etc. in parallel. better approximation; furthermore, our kernels are complementary, they are able to complement each other to learn better feature representation for higher accuracy.

On the other hand, interleaved group convolution (IGC) (Zhang et al. (2017) ) uses group convolution with permutation to leverage the shortage of applying group convolution consecutively, and hence, they achieve better parameter utilization. Logically, CW-SC might be reduced to IGC whose group numbers are 2 for both group convolutions; however, there are a little different in implementation. IGC splits a group convolution and a permutation into two stages but CW-SC embeds the permutation into convolution, which provides more advantages in hardware implementation (ASIC and FPGA) . Permutation process usually involves data movement and hence a temporary buffer might be required to swap data to different addresses. Thus, by embedding the permutation into convolution, our CW-SC has the potential to be more efficient than IGC in implementation even though they achieve identical algorithmic performance. We compare our SW-SC with IGC and the results are shown in Table 7 . We find that the SW-SC surpasses IGC by 1 2% points except for the extreme case (IGC-L100M2), which is similar to XceptionNet. Furthermore, we also integrated IGC with our SW-SC (ResNet-18-sc-IGC-L16M16 (w = 1.5), we can achieve another 1.8% improvement over original IGC-L16M16+Identity, which justify the orthogonality between two works (If we compare with the reproduced IGC-L16M16, we achieve 2.4% improvement without any overhead on computations and parameters.). 

5. CONCLUSION:

We propose an efficient way to utilize model parameters for better accuracy without increasing any computational complexity and parameters. Due to the fact that the proposed sparse-complementary kernel has almost perfect coverage of receptive field only with half of computations, it achieves better results when we increase the number of kernels to match the computation amounts compared to regular convolution. Under the same computational budgets, we always achieve better performance in the classification task. We also demonstrate that the sparse-complementary convolutions can achieve competitive running speed on GPU in practice for most cases. Since our proposed performance boost using simpler kernel shows promising result with high model utilization, it will be worth investigating other types of simpler kernels for improving performance. -comb: combine SW-SC and CW-SC., † :Use the kernel shape in Fig. 6 for SW-SC.

SW-SC kernel:

The SW-Sc kernels are designed to approximate the receptive field of original dense kernels; however, by simply replacing dense kernels by SW-SC, we might degrade algorithmic performance but reduce model complexity. Table 8 compares the original ResNets and the ones use SW-SC without increasing the width (w = 1.0). In most case, SW-SC (w = 1.0) degrades accuracy slightly and sometimes it also improves the performance (ResNet-110 on CIFAR-10); however, SW-SC (w = 1.0) reduces the FLOPs and parameters about 1.8×, which increases model utilization.

Table 9 shows real speedup of SW-SC (w = 1.0) over dense kernels when given the same configuration of an input tensor and a convolutional layer, and the used deep learning framework and measurement methods are identical to section 4.3. Our SW-SC convolution achieve 1.8× speedup theoretically, and our implementation can achieve close speed up as compared to highly-optimized CUDNN when an input tensor with more channels (e.g. configuration D, E and F.).

Combination of SW-SC and CW-SC Due to the orthogonality of SW-SC and CW-SC, we combine them together and evaluate them on CIFAR-10/100. We use ResNet as the base network and use both SW-SC and CW-SC on every 3 × 3 convolutions in the residual block. Thanks to the saving on CW-SC, we can enlarge the network to w = 1.875 (sc-comb); however, each kernel will be too sparse to capture meaningful features (about 25% parameters of the original kernel); therefore, even with more kernels, its performance is only competitive to the one uses only SW-SC on 3 × 3 kernels (See Table 8 for details).

Figure 6 : Another SW-SC kernels.

Other shapes of SW-SC In this paper, for 3 × 3 kernel, we propose to use + and × shape as our base kernels; however, other shapes of sparse kernels might be able to achieve the same receptive field. Thus, we use another set of SW-SC kernels (SW-SC † ) to validate our selection is the better choice according to the nature of computer vision application. SW-SC † is composed of the shapes in Fig. 6 (both are rank-2). As shown in Table 8 , it empirically justifies the inappropriate selection of sparse-complementary kernels degrades the performance. 

:

The model utilization is defined as the proportion of model performance over the amount of required resources (computations and parameters). E.g., suppose that networks A and B achieve the same accuracy, but A needs more parameters and computations than B; in this case, B achieves higher model utilization.

Macro-architecture denotes the topology of a network; micro-architecture means the topology within a layer.

More kernels result in more output channels and hence more input feature maps are at next layer.

The normal ResNet means that the shortcut is added after batch normalization but before activation function.

Figures and Tables:

; Zhou et al. (2016); Liu et al. (2015); Alvarez & Salzmann (2016); Wen et al. (2017); Liu et al. (2017)); or scattering zeros everywhere (Han et al. (2015); Mao et al. (2017); Collins & Kohli (

Figure 1: Different approaches for kernel approximation. (a) Regular convolution, (b) Sequential separate kernels and (c) Mixed-shape kernels. For (b) and (c), the shape of kernels can be arbitrary shape, not limited to 1 × k or k × 1 kernels. The major difference between (b) and (c) is that (c) mixes different shapes of kernels in one layer to extract different features and then the next layer can fuse those distinct features rather than extracting one-type features once, as in (b).

Figure 2: Kernel representations of proposed SW-SC and CW-SC kernels (3 × 3 kernel), gray color denotes the locations of trainable weights. (a) 3D-view of SW-SC kernels, and (b) 2D-view of SW-SC kernels, for a 3 × 3 convolution, the shapes are + and ×. (c) 3D-view of CW-SC kernels, each kernel either samples even-or odd-indexed feature maps for convolution.

Figure 3: Receptive fields of different convolutional kernels of a location at a layer (across multiple channels). (a) Conventional kernels. (b) and (c) apply SW-SC kernels sequentially ((b) applies ×shape at layer L -2 and +-shape at layer L -1, (c) reverses the order in (b)). (d) and (e) use SW-SC kernels. Due to the fact that feature maps from the previous layer are extracted by either even-indexed sparse kernels or odd-indexed sparse kernels, some uncovered receptive field can be recovered by complementary kernels (highlighted by yellow color).

Figure 4: Error rate (%), FLOPs and # of parameters on the CIFAR-10/100 (C10/C100) datasets, including baselines and our wider and deeper networks.

sc (w = 1.3125) / ResNet-194-sc (w = 1.0) 1.080 ResNet-164-sc (w = 1.3125) / ResNet-290-sc (w = 1.0) 1.079

(a) FLOPs vs. Error Rate (b) Parameters vs. Error Rate

Figure 5: Comparison between baselines and our models for all ResNets on ImageNet. Our models consistently provide better accuracy and model utilization.

Comparison with related works.

Table content: <table><tr><td>Related works</td><td>Key features</td><td>Orthogonality to ours  *</td></tr><tr><td>Han et al. (2015); Liu et al. (2015); Collins &amp; Kohli (2014)</td><td>Random sparsity</td><td>Y</td></tr><tr><td>Wen et al. (2016);</td><td/><td/></tr></table>

Error rate (%), FLOPs and # of parameters of DenseNet on the CIFAR-10/100 (C10/C100) and ImageNet datasets. Bold number indicates the best performance among the networks with similar complexity.

Table content: <table><tr><td>Network</td><td>C10</td><td>C100</td><td colspan="3">ImageNet FLOPs (×10 9 ) Params (×10 6 )</td></tr><tr><td>DenseNet-121 (k = 12)</td><td colspan="2">4.01% 21.55%</td><td>-</td><td>0.29</td><td>0.77</td></tr><tr><td>DenseNet-121-sc (k = 12, w = 1.375)</td><td colspan="2">4.24% 20.81%</td><td>-</td><td>0.30</td><td>0.78</td></tr><tr><td>DenseNet-121 (k = 32)</td><td>-</td><td>-</td><td>25.13%</td><td>2.73</td><td>7.97</td></tr><tr><td>DenseNet-121-sc (k = 32, w = 1.3125)</td><td>-</td><td>-</td><td>24.85%</td><td>2.75</td><td>8.16</td></tr></table>

Effective FLOPs ratio of wider and deeper networks (wider/deeper) at the same FLOPs.

Table content: <table><tr><td>Effective FLOPs =</td></tr></table>

Error rate (%) among networks on the CIFAR-10/100 (C10/C100) datasets. Bold number indicates the best performance among the networks with similar complexity. w of all models are set to 1.3125.

Table content: <table><tr><td>Network</td><td>C10</td><td>C100</td></tr><tr><td>ResNet-32-sc</td><td colspan="2">6.26% 28.06%</td></tr><tr><td>ResNet-32-sc-seq</td><td colspan="2">6.36% 28.47%</td></tr><tr><td>ResNet-110-sc</td><td colspan="2">5.32% 25.24%</td></tr><tr><td colspan="3">ResNet-110-sc-seq 5.51% 25.77%</td></tr><tr><td>ResNet-164-sc</td><td colspan="2">5.44% 25.09%</td></tr><tr><td colspan="3">ResNet-164-sc-seq 5.31% 25.15%</td></tr></table>

GPU speed comparison of SW-SC and regular convolution under similiar computations. : N : batch size, C: channels, H: height, W : width. † : k: kernel size, K: number of kernels. Stride and padding in convolutional layers are 1; w is set to 1.3125.

Table content: <table><tr><td>Configuration</td><td>Input tensor N × C × H × W  *</td><td colspan="2">Convolutional layer Speed up k × k, K  †</td></tr><tr><td>A</td><td colspan="2">32 × 672 × 14 × 14 3 × 3, 672 SW-SC 32 × 512 × 14 × 14 3 × 3, 512</td><td>1.00×</td></tr><tr><td>B</td><td>32 × 672 × 7 × 7 32 × 512 × 7 × 7</td><td>3 × 3, 672 SW-SC 3 × 3, 512</td><td>0.99×</td></tr><tr><td>C</td><td colspan="2">32 × 1344 × 7 × 7 3 × 3, 1344 SW-SC 32 × 1024 × 7 × 7 3 × 3, 1024</td><td>1.21×</td></tr><tr><td/><td/><td/><td/></tr></table>

Error rate (%), FLOPs and # of parameters among networks on ImageNet. Single crop validation errors on a 224 × 224 crop is reported. Bold number indicates the best performance among the networks with similar complexity. Only using 1×3 and 3×1 convolutions to replace 3×3 convolutions, so the width ratio is increased.

Table content: <table><tr><td>Network</td><td>Top-1</td><td colspan="3">Top-5 FLOPs (×10 9 ) Params (×10 6 )</td></tr><tr><td>ResNet-50</td><td colspan="2">23.61% 6.85%</td><td>4.09</td><td>25.55</td></tr><tr><td>Ioannou et al. (2016) (w = 1.125)</td><td colspan="2">24.46% 7.42%</td><td>3.86</td><td>24.10</td></tr><tr><td colspan="3">Ioannou et al. (2016)  *  (w = 1.1875) 24.17% 7.23%</td><td>4.00</td><td>24.93</td></tr><tr><td colspan="3">ResNet-50-sc (w = 1.28125) (Ours) 23.35% 6.74%</td><td>3.87</td><td>25.25</td></tr><tr><td/><td/><td/><td/></tr></table>

Error rate (%), FLOPs and # of parameters among networks on ImageNet. Single crop validation errors on a 224 × 224 crop is reported.

Table content: <table><tr><td>Network</td><td>Top-1</td><td>Top-5</td><td colspan="2">FLOPs (×10 9 ) Params (×10 6 )</td></tr><tr><td>ResNet-18</td><td colspan="2">29.66% 10.50%</td><td>1.81</td><td>11.69</td></tr><tr><td>IGC-L4M32+Ident.(Zhang et al. (2017))  *</td><td colspan="2">30.77% 10.99%</td><td>1.90</td><td>11.21</td></tr><tr><td colspan="3">IGC-L16M16+Ident.(Zhang et al. (2017))  *  29.40% 10.99%</td><td>2.20</td><td>11.33</td></tr><tr><td colspan="3">IGC-L16M16+Ident.(Zhang et al. (2017))  † 30.03% 11.21%</td><td>2.26</td><td>13.53</td></tr><tr><td colspan="3">IGC-L100M2+Ident.(Zhang et al. (2017))  *  26.95% 8.92%</td><td>1.3</td><td>8.61</td></tr><tr><td>ResNet-18-sc (w = 1.3125) (Ours)</td><td colspan="2">28.06% 9.80%</td><td>1.79</td><td>11.51</td></tr><tr><td>ResNet-18-sc-IGC-L16M16 (w = 1.5)</td><td colspan="2">27.59% 9.48%</td><td>2.35</td><td>13.15</td></tr><tr><td/><td/><td/><td/></tr></table>

Error rate (%), FLOPs and # of parameters among networks on the CIFAR-10/100 (C10/C100) datasets. Bold number indicates the best performance among the networks with similar complexity.

Table content: <table><tr><td colspan="2">6 SUPPLEMENTARY MATERIALS</td><td/><td/></tr><tr><td colspan="2">6.1 MORE ANALYSIS ON SW-SC AND CW-SC</td><td/><td/></tr><tr><td>Network</td><td>C10</td><td>C100</td><td colspan="2">FLOPs (×10 6 ) Params (×10 6 )</td></tr><tr><td>ResNet-32</td><td colspan="2">6.88% 29.19%</td><td>69.1</td><td>0.47</td></tr><tr><td>ResNet-50-sc (w = 1.0)</td><td colspan="2">6.37% 29.11%</td><td>62.3</td><td>0.43</td></tr><tr><td>ResNet-32-sc-comb (w = 1.875)</td><td colspan="2">6.53% 28.94%</td><td>68.6</td><td>0.47</td></tr><tr><td>ResNet-32-sc  † (w = 1.3125)</td><td colspan="2">6.77% 28.83%</td><td>66.5</td><td>0.45</td></tr><tr><td>ResNet-32-sc (w = 1.0)</td><td colspan="2">7.13% 30.43%</td><td>38.7</td><td>0.26</td></tr><tr><td>ResNet-32-sc (w = 1.3125)</td><td colspan="2">6.26% 28.06%</td><td>66.5</td><td>0.45</td></tr><tr><td>ResNet-110</td><td colspan="2">5.70% 27.38%</td><td>253.1</td><td>1.73</td></tr><tr><td>ResNet-194-sc (w = 1.0)</td><td colspan="2">6.04% 26.60%</td><td>251.1</td><td>1.73</td></tr><tr><td colspan="3">ResNet-110-sc-comb (w = 1.875) 5.39% 25.65%</td><td>248.3</td><td>1.72</td></tr><tr><td>ResNet-110-sc  † (w = 1.3125)</td><td colspan="2">5.56% 25.72%</td><td>242.6</td><td>1.66</td></tr><tr><td>ResNet-110-sc (w = 1.0)</td><td colspan="2">5.51% 27.85%</td><td>141.0</td><td>0.966</td></tr><tr><td>ResNet-110-sc (w = 1.3125)</td><td colspan="2">5.32% 25.24%</td><td>242.6</td><td>1.66</td></tr><tr><td>ResNet-164</td><td colspan="2">5.63% 26.23%</td><td>380.6</td><td>2.62</td></tr><tr><td>ResNet-290-sc (w = 1.0)</td><td colspan="2">5.56% 25.53%</td><td>376.9</td><td>2.59</td></tr><tr><td colspan="3">ResNet-164-sc-comb (w = 1.875) 5.54% 25.31%</td><td>372.7</td><td>2.57</td></tr><tr><td>ResNet-164-sc  † (w = 1.3125)</td><td colspan="2">5.87% 25.59%</td><td>364.6</td><td>2.50</td></tr><tr><td>ResNet-164-sc (w = 1.0)</td><td colspan="2">5.93% 26.60%</td><td>211.7</td><td>1.46</td></tr><tr><td>ResNet-164-sc (w = 1.3125)</td><td colspan="2">5.44% 25.09%</td><td>364.6</td><td>2.50</td></tr></table>

GPU speed up of SW-SC convolution to conventional convolution. : k: kernel size, K: number of kernels.6.2 EXPERIMENTAL RESULTS ON IMAGENETTable10shows the details on the experiments for ImageNet.

Table content: <table><tr><td>Configuration</td><td>Input tensor N × C × H × W  *</td><td colspan="2">Convolutional layer Speedup k × k, K  †</td></tr><tr><td>A</td><td>32 × 256 × 28 × 28</td><td>3 × 3, 256</td><td>1.22×</td></tr><tr><td>B</td><td>32 × 256 × 28 × 28</td><td>3 × 3, 512</td><td>1.40×</td></tr><tr><td>C</td><td>32 × 512 × 14 × 14</td><td>3 × 3, 256</td><td>1.48×</td></tr><tr><td>D</td><td>32 × 512 × 14 × 14</td><td>3 × 3, 512</td><td>1.77×</td></tr><tr><td>E</td><td>32 × 1024 × 7 × 7</td><td>3 × 3, 512</td><td>1.68×</td></tr><tr><td>F</td><td>32 × 1024 × 7 × 7</td><td>3 × 3, 1024</td><td>1.98×</td></tr><tr><td/><td/><td/><td/></tr></table>

Error rate (%), FLOPs and # of parameters among networks on ImageNet. Single crop validation errors on a 224 × 224 crop is reported. Bold number indicates the best performance among the networks with similar complexity.

Table content: <table><tr><td>Network</td><td>Top-1</td><td>Top-5</td><td>FLOPs (×10 9 ) Params (×10 6 )</td></tr></table>

Peer review (iclr2018):
 This paper introduces a new design of kernels in convolutional neural networks. The idea is to have sparse but complementary kernels with predefined patterns, which altogether cover the same receptive field as dense kernels. Because of the sparsity of such kernels, deeper or wider networks can be designed at the same computational cost as networks with dense kernels. Strengths: - The complementary kernels come at no loss compare to standard ones - The resulting wider networks can achieve better accuracies than the original ones Weaknesses: - The proposed patterns are clear for 3x3 kernels, but no solution is proposed for other dimensions - The improvement over the baseline is not very impressive - There is no comparison against other strategies, such as 1xk and kx1 kernels (e.g., Ioannou et al. 2016) Detailed comments: - The separation into + and x patterns is quite clear for 3x3 kernels. However, two such patterns would not be sufficient for 5x5 or 7x7 kernels. This idea would have more impact if it generalized to arbitrary kernel dimensions. - The improvement over the original models are of the order of less than 1 percent. I understand that such improvements are not easy to achieve, but one could wonder if they are not due to the randomness of initialization/mini-batches. It would be more meaningful to report average accuracies and standard deviations over several runs of each experiment. - Section 4.4 briefly discusses the comparison with using 3x1 and 1x3 kernels, mentioning that an empirical comparison is beyond the scope of this paper. To me, this comparison is a must. In fact, the discussion in this section is not very clear to me, as it mentions additional experiments that I could not find (maybe I misunderstood the authors). What I would like to see is the results of a model based on the method of Ioannou et al, 2016 with the same number of FLOPS. - In Section 2, the authors review ideas of so-called random kernel sparsity. Note that the work of Wen et al., 2016, and that of Alvarez & Salzmann, NIPS 2016, do not really impose random sparsity, but rather aim to cancel out entire kernels, thus reducing the size of the model and not requiring implementation overhead. They also do not require pre-training and re-training, but just a single training procedure. Note also that these methods often tend not to decrease accuracy, but rather even increase it (by a similar magnitude to that in this paper), for a more compact model. - In the context of random sparsity, it would be worth citing the work of Collins & Kohli, 2014, Memory Bounded Deep Convolutional Networks. - I am not entirely convinced by the discussion of the grouped sparsity method in Section 3.1. In fact, the order of the channels is arbitrary, since the kernels are learnt. Therefore, it seems to me that they could achieve the same result. Maybe the authors can clarify this? - Is there a particular reason why the central points appears in both complementary kernels (+ and x)? - Why did the authors change the training procedure of ResNets slightly compared to the original paper, i.e., 50k training images instead of 45k training + 5k validation? Did the baseline (original model) reported here also use 50k? What would the results be with 45k? - Fig. 5 is not entirely clear to me. What was the width of each layer? The original one or the modified one? - It would be interesting to report the accuracy of a standard ResNet with 1.325*width as a comparison, as well as the runtime of such a model. - In Table 4, I find it surprising that there is an actual speedup for the model with larger width. I would have expected the same runtime. How do the authors explain this?