summaries: The paper proposes a CNN compression method, based on the so called EHP operation, which can be used to  analyze and generalize depthwise separable convolution. Based on EHP, the paper develops depthwise separable convolution to compress CNNs, and extend it to a rank-k approach with further improved accuracy. Some analysis is provided about the operation equivalence. The experiments on standard benchmark datasets show the effectiveness of the method.  The paper is dedicated to studying fast and lightweight convolution for efficient compression and retaining original accuracy. In this paper, the authors interpret existing convolution methods based on depthwise separable convolution and derive FALCON. They claim their FALCON mathematically approximate the standard convolution kernel and achieves a better TA/efficiency tradeoff. They conduct extensive experiments to show that FALCON based method 1) outperforms previous state-of-the-art methods; 2) achieve 8X efficiency while ensuring similar TA. This paper proposed a model compression method: Falcon and rank-k Falcon. Both are used to compress CNN type of models by replacing standard convolution layer with a compact Falcon or rank-k Falcon layer to compress the model. Falcon's main idea is to decompose the traditional convolution kernel K into two smaller tensors, one is depthwise convolution kernel D and pointwise convolution kernel P. And DP will reconstruct the original kernel K. Since D+P's memory is  D*D*M+N*M which is smaller than the original size D*D*M*N, and thus when N is large, the memory saving could be large. The paper is in general in good writing and very easy to read.
abstractText: How can we efficiently compress Convolutional Neural Networks (CNN) while retaining their accuracy on classification tasks? A promising direction is based on depthwise separable convolution which replaces a standard convolution with a depthwise convolution and a pointwise convolution. However, previous works based on depthwise separable convolution are limited since 1) they are mostly heuristic approaches without a precise understanding of their relations to standard convolution, and 2) their accuracies do not match that of the standard convolution. In this paper, we propose FALCON, an accurate and lightweight method for compressing CNN. FALCON is derived by interpreting existing convolution methods based on depthwise separable convolution using EHP, our proposed mathematical formulation to approximate the standard convolution kernel. Such interpretation leads to developing a generalized version rank-k FALCON which further improves the accuracy while sacrificing a bit of compression and computation reduction rates. In addition, we propose FALCON-branch by fitting FALCON into the previous state-of-the-art convolution unit ShuffleUnitV2 which gives even better accuracy. Experiments show that FALCON and FALCON-branch outperform 1) existing methods based on depthwise separable convolution and 2) standard CNN models by up to 8× compression and 8× computation reduction while ensuring similar accuracy. We also demonstrate that rank-k FALCON provides even better accuracy than standard convolution in many cases, while using a smaller number of parameters and floating-point operations.
references.authors: Eirikur Agustsson Fabian Mentzer Michael Tschannen Lukas Cavigelli Radu Timofte Luca Benini Luc Van Gool
references.title: Soft-to-hard vector quantization for end-to-end learning compressible representations
references.venue: Neural Information Processing Systems (NIPS),
references.authors: Wenlin Chen James T. Wilson Stephen Tyree Kilian Q. Weinberger Yixin Chen
references.title: Compressing neural networks with the hashing trick
references.venue: International Conference on Machine Learning (ICML),
references.authors: Yoojin Choi Mostafa El-Khamy Jungwon Lee
references.title: Towards the limit of network quantization
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Chollet Franois
references.title: Xception: Deep learning with depthwise separable convolutions, 2016
references.venue: URL http://arxiv.org/abs/1610.02357. cite arxiv:1610.02357
references.authors: Matthieu Courbariaux Yoshua Bengio Jean-Pierre David
references.title: Binaryconnect: Training deep neural networks with binary weights during propagations
references.venue: Neural Information Processing Systems (NIPS),
references.authors: Matthieu Courbariaux Itay Hubara Daniel Soudry Ran El-Yaniv Yoshua Bengio
references.title: Binarized neural networks: Training neural networks with weights and activations constrained to +1 or -1
references.venue: Neural Information Processing Systems (NIPS),
references.authors: Song Han Jeff Pool John Tran William J. Dally
references.title: Learning both weights and connections for efficient neural networks
references.venue: Neural Information Processing Systems (NIPS),
references.authors: Song Han Huizi Mao William J. Dally
references.title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Lu Hou Quanming Yao James T. Kwok
references.title: Loss-aware binarization of deep networks
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Andrew G. Howard Menglong Zhu Bo Chen Dmitry Kalenichenko Weijun Wang Tobias Weyand Marco Andreetto Hartwig Adam
references.title: Mobilenets: Efficient convolutional neural networks for mobile vision applications
references.venue: CoRR, abs/1704.04861,
references.authors: Dong Hyun Kim Chanyoung Park Jinoh Oh Sungyoung Lee Hwanjo Yu
references.title: Convolutional matrix factorization for document context-aware recommendation
references.venue: In Recsys,
references.authors: Yong-Deok Kim Eunhyeok Park Sungjoo Yoo Taelim Choi Lu Yang Dongjun Shin
references.title: Compression of deep convolutional neural networks for fast and low power mobile applications
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Alex Krizhevsky Ilya Sutskever Geoffrey E. Hinton
references.title: Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems
references.venue: Annual Conference on Neural Information Processing Systems
references.authors: Vadim Lebedev Yaroslav Ganin Maksim Rakhuba Ivan Oseledets Victor Lempitsky
references.title: Speeding-up convolutional neural networks using fine-tuned cp-decomposition
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Hao Li Asim Kadav Igor Durdanovic Hanan Samet Hans Peter Graf
references.title: Pruning filters for efficient convnets
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Ningning Ma Xiangyu Zhang Hai-Tao Zheng Jian Sun
references.title: Shufflenet V2: practical guidelines for efficient CNN architecture
references.venue: design. CoRR,
references.authors: Pavlo Molchanov Stephen Tyree Tero Karras Timo Aila Jan Kautz
references.title: Pruning convolutional neural networks for resource efficient inference
references.venue: Neural Information Processing Systems (NIPS),
references.authors: Alexander Novikov Dmitry Podoprikhin Anton Osokin Dmitry Vetrov
references.title: Tensorizing neural networks
references.venue: Neural Information Processing Systems (NIPS),
references.authors: Mark Sandler Andrew Howard Menglong Zhu Andrey Zhmoginov Liang-Chieh Chen
references.title: Mobilenetv2: Inverted residuals and linear bottlenecks
references.venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),
references.authors: Laurent Sifre
references.title: Rigid-motion scattering for image classification
references.venue: PhD thesis, cole Polytechnique,
references.authors: Karen Simonyan Andrew Zisserman
references.title: Very deep convolutional networks for large-scale image recognition
references.venue: CoRR, abs/1409.1556,
references.authors: Christian Szegedy Sergey Ioffe Vincent Vanhoucke Alexander A. Alemi
references.title: Inception-v4, inception-resnet and the impact of residual connections on learning
references.venue: In AAAI,
references.authors: Karen Ullrich Edward Meeds Max Welling
references.title: Soft weight-sharing for neural network compression
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Wenpeng Yin Hinrich Schütze Bing Xiang Bowen Zhou
references.title: ABCNN: attention-based convolutional neural network for modeling sentence
references.venue: pairs. TACL,
references.authors: Xiangyu Zhang Xinyu Zhou Mengxiao Lin Jian Sun
references.title: Shufflenet: An extremely efficient convolutional neural network for mobile devices, 2017
references.authors: Chenzhuo Zhu Song Han Huizi Mao William J. Dally
references.title: Trained ternary quantization
references.venue: International Conference on Learning Representations (ICLR),
references.title: 2018) proposed a new convolution architecture which we call as MobileConvV2, in their MobilenetV2 model. MobileConvV2 consists of three sub-layers as shown in Figure 5(b). The first and the third sub-layers are pointwise convolution for adjusting the num
references.authors: Ma
references.title: Comparison of architectures based on depthwise separable convolution. BN denotes batchnormalization, and Relu is an activation function. expansion ratio. The second sub-layer is a D×D depthwise convolution
references.authors: Ma
references.title: 4gH ′W ′N2 FLOPs
references.authors: Ma
references.title: G PARAMETERS AND FLOPS We summarize the numbers of parameters and FLOPs for FALCON and competitors
sections.heading: 1 INTRODUCTION
sections.text: How can we efficiently reduce size and energy consumption of Convolutional Neural Networks (CNN) while maintaining their accuracy on classification tasks? Nowadays, CNN is widely used in various areas including computer vision (Krizhevsky et al. (2012); Simonyan & Zisserman (2014); Szegedy et al. (2017)), natural language processing (Yin et al. (2016)), recommendation system (Kim et al. (2016a)), etc. In addition, model compression has become an important technique due to an increase in the model capacity and the number of parameters in CNN. One recent and promising direction for compressing CNN is depthwise separable convolution (Sifre (2014)) which replaces standard convolution with depthwise and pointwise convolutions. The depthwise convolution applies a separate 2D convolution kernel for each input channel, and the pointwise convolution changes the channel size using 1×1 convolution (details in Section 2.1). Several recent methods (Howard et al. (2017); Sandler et al. (2018); Zhang et al. (2017)) based on depthwise separable convolution show reasonable performances in terms of compression and computation reduction.
  However, existing approaches based on depthwise separable convolution have several crucial limitations. First, they are heuristic methods, and their relation to the standard convolution is not clearly identified. Second, due to their heuristic nature, generalizing the methods is difficult. Third, although they give reasonable compression and computation reduction, their accuracy is not sufficient compared to that of standard-convolution-based models.
  In this paper, we propose FALCON, an accurate and lightweight method for compressing CNN. FALCON overcomes the limitations of the previous methods based on the depthwise separable convolution using the following two main ideas. First, we precisely define the relationship between the standard convolution and the depthwise separable convolution using EHP (Extended Hadamard
  Product), which is our proposed mathematical formulation to correlate the standard convolution kernel with the depthwise convolution kernel and the pointwise convolution kernel. We then design FALCON by fine-tuning and reordering the results of EHP to improve the accuracy of convolution operations. Second, based on the precise definition, we generalize the FALCON to design rank-k FALCON, which further improves accuracy while sacrificing a bit of compression and computation reduction rates. We also propose FALCON-branch by fitting FALCON into the state-of-the-art convolution unit ShuffleUnitV2 which gives even higher accuracy. As a result, FALCON and FALCON-branch provide a superior accuracy compared to other methods based on depthwise separable convolution, with similar compression and computation reduction rates, and rank-k FALCON further improves accuracy, outperforming even the original convolution in many cases. Our contributions are summarized as follows:
  • Generalization. We analyze and generalize depthwise separable convolution to our proposed EHP (Extended Hadamard Product) operation. This generalization enables a precise understanding of the relationship between depthwise separable convolution and standard convolution. Furthermore, with fine-tuning operations, it leads to our proposed method FALCON. • Algorithm. We propose FALCON, a CNN compression method based on depthwise separable convolution. FALCON is carefully designed to compress CNN with little accuracy loss. We also propose rank-k FALCON to further improve the accuracy with a little sacrifice in compression and computation reduction rates. FALCON can be easily integrated into other architectures, and we propose FALCON-branch which combines FALCON with a branch architecture for a better performance. We theoretically analyze the compression and computation reduction rates of FALCON and other competitors. • Experiments. We perform extensive experiments and show that FALCON 1) outperforms other state-of-the-art methods based on depthwise separable convolution for compressing CNN, and 2) provides up to 8× compression and computation reduction compared to the standard convolution while giving similar accuracies. Furthermore, we show that rank-k FALCON provides even better accuracy than the standard convolution in many cases while using a smaller number of parameters and floating-point operations.
  The rest of this paper is organized as follows. Section 2 explains preliminaries. Section 3 describes our proposed method FALCON. Section 4 presents experimental results. After discussing related works in Section 5, we conclude in Section 6.
sections.heading: 2 PRELIMINARY
sections.text: We describe preliminaries on depthwise separable convolution and methods based on depthwise separable convolution. Symbols used in this paper are described in Table 4 of Appendix.
sections.heading: 2.1 DEPTHWISE SEPARABLE CONVOLUTION
sections.text: Depthwise Separable Convolution (DSConv) consists of two sub-layers: depthwise convolution and pointwise convolution. The architecture of each convolution layer in DSConv is illustrated in Figure 5(a). Depthwise convolution (DWConv) kernel consists of several D×D 2-dimensional filters. The number of 2-dimension filters is the same as that of input feature maps. Each filter is applied on the corresponding input feature map, and produces an output feature map. Pointwise convolution (PWConv), known as 1× 1 convolution, is a standard convolution with kernel size 1. DSConv is defined as follows:
  O′h′,w′,m = D∑ i=1 D∑ j=1 Di,j,m · Ihi,wj ,m (1)
  Oh′,w′,n = M∑ m=1 Pm,n ·O′h′,w′,m (2)
  where Di,j,m and Pm,n are depthwise convolution kernel and pointwise convolution kernel, respectively. O′h′,w′,m ∈ RH ′×W ′×M denotes intermediate feature maps. DSConv performs DWConv on
  input feature maps Ihi,wj ,m using equation 1, and generates intermediate feature maps O ′ h′,w′,m. Then, DSConv performs PWConv on O′h′,w′,m using equation 2, and generates output feature maps Oh′,w′,n.
sections.heading: 2.2 METHODS BASED ON DEPTHWISE SEPARABLE CONVOLUTION
sections.text: Several CNN methods have been proposed based on Depthwise Separable Convolution (DSConv) recently. DSConv was first introduced by Sifre (2014). Chollet & Franois (2016) built Xception module using DSConv in a few layers. Howard et al. (2017) built Mobilenet with all convolution layers replaced by DSConv. Sandler et al. (2018) built MobileNetV2 with inverted bottleneck block, denoted as MobileConvV2 in this paper. Zhang et al. (2017) built a CNN model with Shufflenet Unit, denoted as ShuffleUnit in this paper. Ma et al. (2018) improved Shufflenet by designing ShufflenetV2 Unit, denoted as ShuffleUnitV2 in this paper. The architecture and detailed descriptions are in Figure 5 and Appendix D.
sections.heading: 3 PROPOSED METHOD
sections.text: We describe FALCON, our proposed method for compressing CNN. We first define Extended Hadamard Product (EHP), a key mathematical formulation to generalize depthwise separable convolution, in Section 3.1. We interpret depthwise separable convolution used in Mobilenet using EHP in Section 3.2. We propose FALCON in Section 3.3 and explain why FALCON can replace standard convolution. Then, we propose rank-k FALCON, which extends the basic FALCON, in Section 3.4. We show that FALCON can be easily integrated into a branch architecture to compress it with little sacrifice of accuracy in Section 3.5. Finally, we theoretically analyze the performance of FALCON in Appendix C.
sections.heading: 3.1 EXTENDED HADAMARD PRODUCT (EHP)
sections.text: We define Extended Hadamard Product (EHP), a generalized elementwise product for two operands of different shapes, to generalize the formulation of the relation between standard convolution and depthwise separable convolution. Before generalizing the formulation, we give an example of formulating the relation between standard convolution and depthwise separable convolution. Suppose we have a 4-order standard convolution kernel K ∈ RI×J×M×N , a 3-order depthwise convolution kernel D ∈ RI×J×M , and a pointwise convolution kernel P ∈ RM×N . Let Ki,j,m,n be (i, j,m, n)-th element of K, Di,j,m be (i, j,m)-th element of D, and Pm,n be (m,n)-th element of P. Then, it can be shown that applying depthwise convolution with D and pointwise convolution with P is equivalent to applying standard convolution kernel K where Ki,j,m,n = Di,j,m · Pm,n (see Section 3.2 for detailed proof).
  To formally express this relation, we define Extended Hadamard Product (EHP) as follows.
  Definition 1 (Extended Hadamard Product). Given p-order tensor D ∈ RI1×···×Ip−1×M and qorder tensor P ∈ RM×J1×···×Jq−1 , the Extended Hadamard Product D E P of D and P is defined to be the tensor K ∈RI1×...×Ip−1×M×J1×...×Jq−1 where the last axis of D and the first axis of P are the common axes such that
  Ki1,...,ip−1,m,j1,...,jq−1 = Di1,...,ip−1,m ·Pm,j1,...,jq−1 for all elements of K.
  Contrary to Hadamard Product which is defined only if the shapes of the two operands are the same, Extended Hadamard Product (EHP) deals with tensors of different shapes. Now, we define a special case of Extended Hadamard Product (EHP) for a third-order tensor and a matrix.
  Definition 2 (Extended Hadamard Product for a third order tensor and a matrix). Given a thirdorder tensor D ∈ RI×J×M and a matrix P ∈ RM×N , the Extended Hadamard Product D E P is defined to be the tensor K ∈RI×J×M×N where the third axis of the tensor D and the first axis of the matrix P are the common axes such that
  Ki,j,m,n = Di,j,m ·Pm,n. for all elements of K.
  We will see that the depthwise separable convolution in Mobilenet can be easily expressed with EHP in Section 3.2; we also propose a new architecture FALCON based on EHP in Section 3.3. EHP is also a core operation that helps us understand other convolution architectures including MobilenetV2 and Shufflenet (see Appendix E).
sections.heading: 3.2 DEPTHWISE SEPARABLE CONVOLUTION AND EHP
sections.text: In this section, we discuss how to represent the convolution layer of Mobilenet as Extended Hadamard Product (EHP) described in Section 3.1. We interpret the depthwise separable convolution, which is the convolution of Mobilenet, as an application of EHP. This interpretation leads to designing a better convolution architecture FALCON in Section 3.3.
  We represent the relationship between standard convolution kernel K ∈ RD×D×M×N and depthwise separable convolution consisting of depthwise convolution kernel D ∈ RD×D×M and pointwise convolution kernel P ∈ RM×N using one EHP operation. Figure 2(a) illustrates the relationship between standard convolution and depthwise separable convolution used in Mobilenet. We show that applying depthwise separable convolution with D and P is equivalent to applying standard convolution with a kernel K which is constructed from D and P.
  Theorem 1. Applying depthwise separable convolution with depthwise convolution kernel D ∈ RD×D×M and pointwise convolution kernel P ∈ RM×N is equivalent to applying standard convolution with kernel K = D E P.
  Proof. See Appendix B.1.
sections.heading: 3.3 FAST AND LIGHTWEIGHT CONVOLUTION (FALCON)
sections.text: We propose FALCON (FAst and Lightweight CONvolution), a novel lightweight convolution that replaces standard convolution. FALCON is an efficient method with fewer parameters and computations than those that the standard convolution requires. In addition, FALCON has better accuracy than competitors while having similar compression and computation reduction rates. The main idea of FALCON is 1) to carefully align depthwise and pointwise convolutions, and 2) initialize kernels using the convolution kernels of the trained standard model. We observe that a typical convolution has more output channels than input channels. In such a setting, performing depthwise convolution after pointwise convolution would allow the depthwise convolution to extract more features from richer feature space; on the other hand, performing pointwise convolution after depthwise convolution as in Mobilenet only combines features extracted from a limited feature space. Based on the observation, FALCON first applies pointwise convolution to generate an intermediate tensor O′ ∈ RH×W×N and then applies depthwise convolution.
  We represent the relationship between standard convolution kernel K ∈ RD×D×M×N and FALCON by applying an EHP operation on pointwise convolution kernel P ∈ RN×M and depthwise convolution kernel D ∈ RD×D×N in Figure 2(b). In FALCON, the kernel K is represented by EHP of D and P as follows:
  K = TT(1,2,4,3)(D E P) s.t. Ki,j,m,n = Pn,m ·Di,j,n. where TT(1,2,4,3) indicates tensor transpose operation to permute the third and the fourth dimensions of a tensor. Note that the common axis is the output channel axis of the standard convolution, unlike EHP for depthwise separable convolution where the common axis is the input channel axis of the standard convolution.
  As in Section 3.2, we show that applying FALCON is equivalent to applying standard convolution with a specially constructed kernel.
  Theorem 2. FALCON which applies pointwise convolution with kernel P ∈ RN×M and then depthwise convolution with kernel D ∈ RD×D×N is equivalent to applying standard convolution with kernel K = TT(1,2,4,3)(D E P).
  Proof. See Appendix B.2.
  Based on the equivalence, we initialize pointwise convolution and depthwise convolution kernels D and P of FALCON by fitting them to the convolution kernels of the trained standard model; i.e., D,P = argminD′,P′ ||K−TT(1,2,4,3)(D′ E P′)||F . After pointwise convolution and depthwise convolution, we add batch-normalization and ReLU activation function as shown in Figure 1(b). We note that FALCON significantly reduces the numbers of parameters and FLOPs compared to standard convolution, which we discuss at Appendix C.
  3.4 RANK-k FALCON
  We propose rank-k FALCON, an extended version of FALCON that improves accuracy while sacrificing a bit of compression and computation reduction rates. The main idea is to perform k independent FALCON operations and sum up the result. Then, we apply batch-normalization (BN) and ReLU activation function to the summed result. Since each FALCON operation requires independent parameters for pointwise convolution and depthwise convolution, the number of parameters increases and thus the compression and the computation reduction rates decrease; however, it improves accuracy by enlarging the model capacity. We formally define the rank-k FALCON with EHP as follows.
  Definition 3 (Rank-k FALCON with Extended Hadamard Product). Rank-k FALCON expresses standard convolution kernel K ∈ RD×D×M×N as EHP of depthwise convolution kernel D(i) ∈
  RD×D×N and pointwise convolution kernel P(i) ∈ RN×M for i = 1, 2, ..., k such that
  K = k∑ i=1 TT(1,2,4,3)(D (i) E P(i)) s.t. Ki,j,m,n = k∑ i=1 P(i)n,m ·D (i) i,j,n
  Figure 2(c) illustrates the relation between standard convolution and rank-k FALCON. For each i = 1, 2, ..., k, we construct the tensor K(i) using EHP of the depthwise convolution kernel D(i) and the pointwise convolution kernel P(i). Then, we construct the standard kernel K by the elementwise sum of the tensors K(i) for all i.
sections.heading: 3.5 FALCON-BRANCH
sections.text: FALCON can be easily integrated into a CNN architecture called standard convolution operation with a branch (StConv-branch), which consists of two branches: standard convolution on the left branch and a residual connection on the right branch (see Figure 1(c)). Ma et al. (2018) improved the performance of CNN by applying depthwise and pointwise convolutions on the left branch of StConv-branch. Since FALCON replaces standard convolution, we observe that StConv-branch can be easily compressed by applying FALCON on the left branch.
  StConv-branch first splits an input in half along the depth dimension. A standard convolution operation is applied to one half, and no operation to the other half. The two are concatenated along the depth dimension, and an output is produced by shuffling the channels of the concatenated tensor. FALCON-branch (see Figure 1(d)) is constructed by replacing the standard convolution branch (left branch) of StConv-branch with FALCON. Advantages of FALCON-branch are that 1) the branch architecture improves the efficiency since convolutions are applied to only half of input feature maps and that 2) FALCON further compresses the left branch effectively. FALCON-branch is initialized by fitting FALCON to the standard convolution kernel of the left branch of StConv-branch.
sections.heading: 4 EXPERIMENTS
sections.text: We validate the performance of FALCON through extensive experiments. We aim to answer the following questions:
  • Q1. Accuracy vs. Compression (Section 4.3). What are the accuracy and the compression tradeoffs of FALCON, FALCON-branch, and competitors? Which method gives the best accuracy for a given compression rate? • Q2. Accuracy vs. Computation (Section 4.4). What are the accuracy and the computation tradeoffs of FALCON, FALCON-branch, and competitors? Which method gives the best accuracy for a given amount of computation? • Q3. Rank-k FALCON (Section 4.5). How do the accuracy, the number of parameters, and the number of FLOPs change as the rank k increases in FALCON?
sections.heading: 4.1 EXPERIMENTAL SETUP
sections.text: Datasets. We perform image classification task on four famous datasets - CIFAR10, CIFAR100, SVHN, and ImageNet. Detailed information of these datasets is described in Table 1.
  Models. For CIFAR10, CIFAR100, and SVHN datasets, we choose VGG19 and ResNet34 to evaluate the performance. We shrink the sizes of both models since the sizes of these three datasets are smaller than that of Imagenet. In VGG19, we reduce the number of fully connected layers and the number of features in fully connected layers: three large fully connected layers (4096-4096-1000) in VGG19 are replaced with two small fully connected layers (512-10 or 512-100). In ResNet34, we remove the first 7 × 7 convolution layer and max-pooling layer since the input size (32 × 32) of these datasets is smaller than the input size (224 × 224) of ImageNet. On both models, we replace all standard convolution layers (except for the first convolution layer) with those of FALCON or other competitors in order to compress and accelerate the model. For ImageNet, we choose VGG16 BN (VGG16 with batch normalization after every convolution layer) and ResNet18. We use the pretrained model from Pytorch model zoo as the baseline model with standard convolution, and replace the standard convolution with other types of convolutions.
  Competitors. We compare FALCON and FALCON-branch with four convolution units consisting of depthwise convolution and pointwise convolution: DSConv, MobileConvV2, ShuffleUnit, and ShuffleUnitV2 (see Figure 5, Section 2.1, and Appendix D for more details). To evaluate the effectiveness of fitting depthwise and pointwise convolution kernels to standard convolution kernel, we build EHP-in which is DSConv where kernels D and P are fitted from the pretrained standard convolution kernel K; i.e., D,P = argminD′,P′ ||K−D′ E P′||F .
  Implementation. We construct all models using Pytorch framework. All the models are trained and tested on GeForce GTX 1080 Ti GPU.
sections.heading: 4.2 FITTING CONVOLUTION UNIT INTO MODEL
sections.text: We evaluate the performance of FALCON against DSConv, MobileConvV2, ShuffleUnit, and ShuffleUnitV2. We take each standard convolution layer (StConv) as a unit, and replace StConv with those from FALCON or other competitors. We evaluate the classification accuracy, the number of parameters in the model, and the number of FLOPs needed for forwarding one image. We only explain how to apply FALCON in this section. The details of how to fit other convolution units into the models are described in Appendix F.
  FALCON. When replacing StConv with FALCON, we use the same setting as that of StConv. I.e., if there are BN and ReLU after StConv, we add BN and ReLU at the end of FALCON; if there is only ReLU after StConv, we add only ReLU at the end of FALCON. This is because FALCON is initialized by approximating the StConv kernel using EHP. Using the same setting for BN and ReLU as StConv is more efficient for FALCON to approximate the StConv. We initialize the pointwise convolution kernel and the depthwise convolution kernel of FALCON by approximating the pretrained standard convolution kernel using EHP. The approximation process is as follows: 1) we first initialize the pointwise convolution kernel and the depthwise convolution kernel randomly, and 2) the pointwise convolution kernel and the depthwise convolution kernel are updated using gradient descent such that the mean squared error of their EHP product and the standard convolution kernel is minimized. Rank-k FALCON uses the same initialization method.
sections.heading: 4.3 ACCURACY VS. COMPRESSION
sections.text: We evaluate the accuracy and the compression rate of FALCON and competitors. Table 2 shows the results on four image datasets. Note that FALCON or FALCON-branch provides the highest accuracy in 7 out of 8 cases while using similar or smaller number of parameters than competitors. Specifically, FALCON and FALCON-branch achieve up to 8× compression rates with less than 1% accuracy drop compared to that of the standard convolution (StConv). Figure 3 shows the tradeoff between accuracy and the number of parameters. Note that FALCON and FALCON-branch show the best tradeoff (closest to the “best” point) between accuracy and compression rate, giving the highest accuracy with similar compression rates.
  Ablation study. We perform an ablation study on two components: 1) the order of depthwise and pointwise convolutions, and 2) initialization. We observe that with a similar number of parameters, 1) FALCON and FALCON without initialization always result in better accuracy than EHP-in and
  DSC, respectively, and 2) EHP-in always results in better accuracy than DSC. Furthermore, FALCON results in better accuracy than FALCON without initialization in 6 out of 8 cases. These observations prove our claims in Section 3.3 that 1) EHP-out (FALCON) is more efficient than EHP-in, and 2) the fitting and the initialization of kernels using EHP improves accuracy. Additionally, we observe that overall performance is more sensitive towards ordering compared to initialization.
sections.heading: 4.4 ACCURACY VS. COMPUTATION
sections.text: We evaluate the accuracy and the amount of computation of FALCON and competitors. We use the number of multiply-adds floating point operations (FLOPs) needed for forwarding one image to a model as the metric of computation. Table 2 also shows the accuracies and the number of FLOPs of methods on four image datasets. Note that FALCON or FALCON-branch provide the highest accuracy in 7 out of 8 cases while using similar FLOPs as competitors do. Compared to StConv, FALCON and FALCON-branch achieve up to 8× FLOPs reduction across different models on different datasets. Figure 4 shows the tradeoff between accuracy and the number of FLOPs. Note that FALCON and FALCON-branch show the best tradeoff (closest to the “best” point) between accuracy and computation, giving the highest accuracy with a similar number of FLOPs.
sections.heading: 4.5 RANK-K FALCON
sections.text: We evaluate the performance of rank-k FALCON by increasing the rank k and monitoring the changes in the numbers of parameters and FLOPs. In Table 3, we observe three trends as the rank k increases: 1) the accuracy becomes higher than that of rank-1 FALCON, 2) the number of parameters increases,
  and 3) the number of floating point operations (FLOPs) increases. Although the rank k that gives the best tradeoff of rank and compression/computation reduction varies, rank-k FALCON improves the accuracy of FALCON in all cases. Especially, we note that rank FALCON often gives even higher accuracy than the standard convolution, while using smaller number of parameters and FLOPs. For example, rank-3 FALCON applied to VGG19 on CIFAR100 dataset shows 1.31 percentage point higher accuracy compared to the standard convolution, with 2.8× smaller number of parameters and 2.8× smaller number of FLOPs. Thus, rank-k FALCON is a versatile method to further improve the accuracy of FALCON while sacrificing a bit of compression and computation.
sections.heading: 5 RELATED WORK
sections.text: Over the past several years, a lot of studies focused on compressing and accelerating DNN to reduce model size, running time, and energy consumption.
  It is believed that DNNs are over-parameterized. Weight-sharing (Han et al. (2016); Ullrich et al. (2017); Chen et al. (2015); Choi et al. (2017); Agustsson et al. (2017)) is a common compression
  method which stores only assignments and centroids of weights. While using the model, weights are loaded according to assignments and centroids. Pruning (Han et al. (2014); Li et al. (2016)) aims at removing useless weights or setting them to zero. Although weight-sharing and pruning can significantly reduce the model size, they are not efficient in reducing the amount of computation. Quantizing (Courbariaux et al. (2015; 2016); Hou et al. (2017); Zhu et al. (2017)) the model into binary or ternary weights reduces model size and computation simultaneously: replacing arithmetic operations with bit-wise operations remarkably accelerates the model.
  Layer-wise approaches are also employed to efficiently compress models. A typical example of such approaches is low-rank approximation (Lebedev et al. (2015); Kim et al. (2016b); Novikov et al. (2015)); it treats the weights as a tensor and uses general tensor approximation methods to compress the tensor. To reduce computation, approximation methods should be carefully chosen, since some of approximation methods may increase computation of the model.
  Compressing existing models has limitations since they are originally designed to be deep and large to give high accuracy. A recent trend is to design a brand new architecture that is small and efficient. Mobilenet (Howard et al. (2017)), MobilenetV2 (Sandler et al. (2018)), Shufflenet (Zhang et al. (2017)), and ShufflenetV2 (Ma et al. (2018)) are the most representative approaches, and they use depthwise convolution and pointwise convolution as building blocks for designing convolution layers. Our proposed FALCON gives a thorough interpretation of depthwise convolution and pointwise convolution, and applies them into model compression, giving the best accuracies with regard to compression and computation.
sections.heading: 6 CONCLUSION
sections.text: We propose FALCON, an accurate and lightweight convolution method to replace standard convolution. By interpreting existing convolution methods based on depthwise separable convolution using EHP operation, FALCON and its general version rank-k FALCON provide accurate and efficient compression on CNN. We also propose FALCON-branch, a variant of FALCON integrated into a branch architecture of CNN for model compression. Extensive experiments show that FALCON and its variants give the best accuracy for a given number of parameter or computation, outperforming other convolution models based on depthwise separable convolution. Compared to the standard convolution, FALCON and FALCON-branch give up to 8× compression and 8× computation reduction while giving similar accuracy. We also show that rank-k FALCON provides better accuracy than the standard convolution, while using smaller numbers of parameters and computations.
sections.heading: A CONVOLUTIONAL NEURAL NETWORK
sections.text: Convolutional Neural Network (CNN) is a type of deep neural network used mainly for structured data. CNN uses convolution operation in convolution layers. In the following, we discuss CNN when applied to typical image data with RGB channels.
  Each convolution layer has three components: input feature maps, convolution kernel, and output feature maps. The input feature maps I ∈ RH×W×M and the output feature maps O ∈ RH′×W ′×N are 3-dimensional tensors, and the convolution kernel K ∈ RD×D×M×N is a 4-dimensional tensor. The convolution operation is defined as:
  Oh′,w′,n = D∑ i=1 D∑ j=1 M∑ m=1 Ki,j,m,n · Ihi,wj ,m (3)
  where the relations between height hi and width wj of input, and height h′ and width w′ of output are as follows:
  hi = (h ′ − 1)s+ i− p and wj = (w′ − 1)s+ j − p (4)
  where s is the stride size, and p is the padding size. The third and the fourth dimensions of the convolution kernel K must match the number M of input channels, and the number N of output channels, respectively.
  Convolution kernel K can be seen as N 3-dimensional filters Fn ∈ RD×D×M . Each filter Fn in kernel K performs convolution operation while sliding over all spatial locations on input feature maps. Each filter produces one output feature map.
sections.heading: B PROOFS OF THEOREMS
sections.text: B.1 PROOF OF THEOREM 1
  Proof. From the definition of EHP, Ki,j,m,n = Di,j,m ·Pm,n. Based on equation 3, we replace the kernel Ki,j,m,n with the depthwise convolution kernel Di,j,m and the pointwise convolution kernel Pm,n.
  Oh′,w′,n = D∑ i=1 D∑ j=1 M∑ m=1 Di,j,m ·Pm,n · Ihi,wj ,m
  where Ihi,wj ,m is the (hi, wj ,m)-th entry of the input. We split the above equation into the following two equations.
  O′h′,w′,m = D∑ i=1 D∑ j=1 Di,j,m · Ihi,wj ,m (5)
  Oh′,w′,n = M∑ m=1 Pm,n ·O′h′,w′,m (6)
  where O′h′,w′,m ∈ RH ′×W ′×M is an intermediate tensor. Note that equation 5 and equation 6 correspond to the depthwise convolution and the pointwise convolution, respectively. Therefore, the output O′h′,w′,m is equal to the output applying depthwise separable convolution used in Mobilenet.
  B.2 PROOF OF THEOREM 2
  Proof. From equation 3, we replace the kernel Ki,j,m,n with the pointwise convolution kernel P and the depthwise convolution kernel D.
  Oh′,w′,n = M∑ m=1 D∑ i=1 D∑ j=1 Pm,n ·Di,j,n · Ihi,wj ,m
  where Ihi,wj ,m is the (hi, wj ,m)-th entry of the input I. We split the above equation into the following two equations.
  O′hi,wj ,n = M∑ m=1 Pm,n · Ihi,wj ,m (7)
  Oh′,w′,n = D∑ i=1 D∑ j=1 Di,j,n ·O′hi,wj ,n (8)
  where I, O′, and O are the input, the intermediate, and the output tensors of convolution layer, respectively. Note that equation 7 and equation 8 correspond to pointwise convolution and depthwise convolution, respectively. Therefore, the output Oh′,w′,n is equal to the output applying FALCON.
sections.heading: C QUANTITATIVE ANALYSIS
sections.text: In this section, we evaluate the compression and the computation reduction of FALCON and rank-k FALCON. All the analysis is based on one convolution layer. The comparison of the numbers of parameters and FLOPs of FALCON and other competitors is in Appendix G.
  C.1 FALCON
  We analyze the compression and the computation reduction rates of FALCON in Theorems 3 and 4.
  Theorem 3. Compression Rate (CR) of FALCON is given by
  CR = # of parameters in standard convolution
  # of parameters in FALCON =
  D2MN
  MN +D2N
  where D2 is the size of standard kernel, M is the number of input channels, and N is the number of output channels.
  Proof. Standard convolution kernel has D2MN parameters. FALCON includes pointwise convolution and depthwise convolution which requires MN and D2N parameters, respectively. Thus, the compression rate of FALCON is CR = D2MN
  MN +D2N .
  Theorem 4. Computation Reduction Rate (CRR) of FALCON is described as:
  CRR = # of FLOPs in standard convolution
  # of FLOPs in FALCON
  = H ′W ′MD2N
  HWMN +H ′W ′D2N where H ′ and W ′ are the height and the width of output, respectively, and H and W are the height and the width of input, respectively.
  Proof. The standard convolution operation requires H ′W ′D2MN FLOPs (Molchanov et al. (2017)). FALCON includes pointwise convolution and depthwise convolution. Pointwise convolution has kernel size D = 1 with stride s = 1 and no padding, so the intermediate tensor O′ has the same height and width as those of the input feature maps. Thus, pointwise convolution needs HWMN FLOPs. Depthwise convolution has the number of input channel M = 1, so it needs H ′W ′D2N FLOPs. The total FLOPs of FALCON is HWMN +H ′W ′D2N , thus the computation reduction rate of FALCON is CRR = H ′W ′D2MN
  HWMN +H ′W ′D2N .
  C.2 RANK-K FALCON
  We analyze the compression and computation reduction rates of rank-k FALCON in Theorem 5.
  Theorem 5. Compression Rate (CRk) and Computation Reduction Rate (CRRk) of rank-k FALCON are described as:
  CRk = CR
  k CRRk =
  CRR
  k
  Proof. The numbers of parameters and FLOPs increase for k times since rank-k FALCON duplicates FALCON for k times. Thus, the compression rate and the computation reduction rate are calculated as CRk = CR
  k and CRRk =
  CRR
  k .
sections.heading: D DESCRIPTION OF RELATED CONVOLUTION UNITS
sections.text: MobileNetV2. Sandler et al. (2018) proposed a new convolution architecture which we call as MobileConvV2, in their MobilenetV2 model. MobileConvV2 consists of three sub-layers as shown in Figure 5(b). The first and the third sub-layers are pointwise convolution for adjusting the number of channels. The first sub-layer expands the number of channels from M to tM , where t is an
  expansion ratio. The second sub-layer is a D×D depthwise convolution. Since depthwise convolution cannot change the number of channels, the third sub-layer adjusts the number of channels from tM to N . There is a shortcut connection between the input, and the output of the third sub-layer to facilitate flow of gradient across multiple layers. MobileConvV2 needs tM2 + D2tM + tMN parameters and tHWM2 + tH ′W ′D2M + tH ′W ′MN FLOPs.
  ShuffleNet. Zhang et al. (2017) proposed a computation-efficient CNN architecture named Shufflenet. As shown in Figure 5(c), each unit of Shufflenet (we call it ShuffleUnit) consists of three sublayers, first group pointwise convolution, depthwise convolution, and second group pointwise convolution, as well as a shortcut. The number of depthwise convolution channels is 14 of output channels N . ShuffleUnit uses group convolution in two pointwise convolution layers to reduce the parameters and FLOPs. However, it is hard to exchange information among groups when group convolutions are stacked. To deal with this problem, ShuffleUnit adds a channel shuffle layer after the first pointwise group convolution. The channel shuffle layer rearranges the order of channels. making it possible to obtain information from different groups. The number of groups is represented as g. ShuffleUnit needs 14gMN+ 1 4D 2N+ 14gN 2 parameters and 14gHWMN+ 1 4H ′W ′D2N+ 14gH ′W ′N2 FLOPs.
  ShufflenetV2. Ma et al. (2018) proposed a practically efficient CNN architecture ShufflenetV2. As shown in Figure 5(d), each unit of ShufflenetV2 (we call it ShuffleUnitV2) consists of two branches. The left branch consists of two pointwise convolutions and one depthwise convolution like MobileConvV2, and the right branch is an identity operation. Note that outputs of both branches maintain the number of channels as M/2. The final output is produced by concatenating and shuffling the output tensors from both of the branches. ShuffleUnitV2 needs 12 (M
  2+D2M) parameters and 12HW (M 2 +D2M) FLOPs.
sections.heading: E GENERALITY OF EHP
sections.text: We show that EHP is a key operation to understand other convolution architectures based on depthwise separable convolution.
  MobilenetV2. As shown in Figure 5(b), MobilenetV2 has an additional pointwise convolution before depthwise convolution in Mobilenet: one layer of MobilenetV2 consists of two pointwise convolutions and one depthwise convolution. In another point of view, MobilenetV2 can be understood as FALCON followed by additional pointwise convolution; i.e., MobilenetV2 performs EHP operation as FALCON does, and performs additional pointwise convolution after that.
  Shufflenet. As shown in Figure 5(c), Shufflenet consists of depthwise convolution and pointwise group convolution which is a variant of pointwise convolution. We represent the convolution layer of Shufflenet using EHP as follows. Let g be the number of groups. We divide the standard convolution
  kernel K ∈ RD×D×M×N into g group standard convolution kernels. Then, the relation of g-th group standard convolution kernel Kg ∈ RD×D× M g × N g with regard to g-th depthwise convolution kernel Dg ∈ RD×D× M g and g-th pointwise group convolution kernel Pg ∈ R M g × N g is
  Kg = Dg E Pg s.t. Kgi,j,mg,ng = D g i,j,mg ·Pgmg,ng
  where mg = 1, 2, ..., Mg and ng = 1, 2, ..., N g . Each group standard convolution is equivalent to the combination of a depthwise convolution and a pointwise convolution, and thus easily expressed with EHP as in Mobilenet.
  Therefore, each layer of Shufflenet is equivalent to the layer consisting of one group convolution followed by standard convolution.
  ShufflenetV2. As shown in Figure 5(d), the left branch of ShufflenetV2 has the same convolutions as in MobilenetV2: it consists of two pointwise convolutions and one depthwise convolution. Like MobilenetV2, the left branch of ShufflenetV2 can be understood as FALCON followed by additional pointwise convolution.
sections.heading: F FITTING OTHER CONVOLUTION UNITS INTO MODELS
sections.text: DSConv. DSConv (shown in Figure 5(a)) has the most similar architecture as FALCON among competitors, and thus DSConv has nearly the same number of parameters as that of FALCON. As in the setting of FALCON, the existence of BN and ReLU at the end of DSConv depends on that of StConv.
  MobileConvV2. In MobileConvV2 architecture (shown in Figure 5(b)), we adjust the numbers of parameters and FLOPs by changing the expansion ratio t as described in Appendix D, which is represented as ‘MobileConvV2-t’. We choose t = 0.5 as the baseline MobileConvV2 to compare with FALCON, since two pointwise convolutions bring lots of parameters and FLOPs to MobileConvV2.
  ShuffleUnit. In ShuffleUnit (shown in Figure 5(c)), we adjust the numbers of parameters and FLOPs by changing the width multiplier α (Howard et al. (2017)) and the number of groups g, which is represented as ‘ShuffleUnit α×(g=g)’. Note that the width multiplier is used to adjust the number of input channels M and the number of output channels N of a convolution layer; if the width multiplier is α, the numbers of input and output channels become αM and αN , respectively. While experimenting with ResNet, we find that ShuffleUnit does not cooperate well with ResNet: ResNet34 with ShuffleUnit does not converge. We suspect that residual block and ShuffleUnit may conflict with each other because of redundant residual connections: the gradient may not find the right path towards previous layers. For this reason, we delete the shortcut of all residual blocks in ResNet34 when using ShuffleUnit.
  ShuffleUnitV2. In ShuffleUnitV2 (shown in Figure 5(d)),we also adjust the number of parameters and FLOPs by changing the width multiplier α, which is represented as ’ShuffleUnitV2 α×’. Other operations of ShuffleUnitV2 stay the same as in Ma et al. (2018).
sections.heading: G PARAMETERS AND FLOPS
sections.text: We summarize the numbers of parameters and FLOPs for FALCON and competitors in Table 5.