AdderNet: Do We Really Need Multiplications in Deep Learning?

Introduction

Given the advent of Graphics Processing Units (GPUs), deep convolutional neural networks (CNNs) with billions of floating number multiplications could receive speed-ups and make important strides in a large variety of computer vision tasks, e.g. image classification , object detection , segmentation , and human face verification . However, the high-power consumption of these high-end GPU cards (e.g. 250W+ for GeForce RTX 2080 Ti) has blocked modern deep learning systems from being deployed on mobile devices, e.g. smart phone, camera, and watch. Existing GPU cards are far from svelte and cannot be easily mounted on mobile devices. Though the GPU itself only takes up a small part of the card, we need many other hardware for supports, e.g. memory chips, power circuitry, voltage regulators and other controller chips. It is therefore necessary to study efficient deep neural networks that can run with affordable computation resources on mobile devices.

Addition, subtraction, multiplication and division are the four most basic operations in mathematics. It is widely known that multiplication is slower than addition, but most of the computations in deep neural networks are multiplications between float-valued weights and float-valued activations during the forward inference. There are thus many papers on how to trade multiplications for additions, to speed up deep learning. The seminal work proposed BinaryConnect to force the network weights to be binary (e.g.-1 or 1), so that many multiply-accumulate operations can be replaced by simple accumulations. After that, Hubara et al. proposed BNNs, which binarized not only weights but also activations in convolutional neural networks at run-time. Moreover, Rastegari et al. introduced scale factors to approximate convolutions using binary operations and outperform by large margins. Zhou et al. utilized low bit-width gradient to accelerate the training of binarized networks. Cai et al. proposed an half-wave Gaussian quantizer for forward approximation, which achieved much closer performance to full precision networks.

Though binarizing filters of deep neural networks significantly reduces the computation cost, the original recognition accuracy often cannot be preserved. In addition, the training procedure of binary networks is not stable and usually requests a slower convergence speed with a small learning rate. Convolutions in classical CNNs are actually cross-correlation to measure the similarity of two inputs. Researchers and developers are used to taking convolution as a default operation to extract features from visual data, and introduce various methods to accelerate the convolution, even if there is a risk of sacrificing network capability. But there is hardly no attempt to replace convolution with another more efficient similarity measure that is better to only involve additions. In fact, additions are of much lower computational complexities than multiplications. Thus, we are motivated to investigate the feasibility of replacing multiplications by additions in convolutional neural networks.

This paper is organized as follows. Section 2 investigates related works on network compression. Section 3 proposes Adder Networks which replace the multiplication in the conventional convolution filters with addition. Section 4 evaluates the proposed AdderNets on various benchmark datasets and models and Section 5 concludes this paper.

Related works

To reduce the computational complexity of convolutional neural networks, a number of works have been proposed for eliminating useless calculations.

Pruning based methods aims to remove redundant weights to compress and accelerate the original network. Denton et al. decomposed weight matrices of fully-connected layers into simple calculations by exploiting singular value decomposition (SVD). Han et al. proposed discarding subtle weights in pre-trained deep networks to omit their original calculations without affecting the performance. Wang et al. further converted convolution filters into the DCT frequency domain and eliminated more floating number multiplications. In addition, Hu et al. discarded redundant filters with less impacts to directly reduce the computations brought by these filters. Luo et al. discarded redundant filters according to the reconstruction error. He et al. utilized a LASSO regression to select important channels by solving least square reconstruction. Zhuang et al. introduce additional losses to consider the discriminative power of channels and selected the most discriminative channels for the portable network.

Instead of directly reducing the computational complexity of a pre-trained heavy neural network, lot of works focused on designing novel blocks or operations to replace the conventional convolution filters. Iandola et al. introduced a bottleneck architecture to largely decrease the computation cost of CNNs. Howard et al. designed MobileNet, which decompose the conventional convolution filters into the point-wise and depth-wise convolution filters with much fewer FLOPs. Zhang et al. combined group convolutions and a channel shuffle operation to build efficient neural networks with fewer computations. Hu et al. proposed the squeeze and excitation block, which focuses on the relationship of channels by modeling interdependencies between channels, to improve the performance at slight additional computational cost. Wu et al. presented a parameter-free “shift” operation with zero flop and zero parameter to replace conventional filters and largely reduce the computational and storage cost of CNNs. Zhong et al. further pushed the shift-based primitives into channel shift, address shift and shortcut shift to reduce the inference time on GPU while keep the performance. Wang et al. developed versatile convolution filters to generate more useful features utilizing fewer calculations and parameters.

Besides eliminating redundant weights or filters in deep convolutional neural networks, Hinton et al. proposed the knowledge distillation (KD) scheme, which transfer useful information from a heavy teacher network to a portable student network by minimizing the Kullback-Leibler divergence between their outputs. Besides mimic the final outputs of the teacher networks, Romero et al. exploit the hint layer to distill the information in features of the teacher network to the student network. You et al. utilized multiple teachers to guide the training of the student network and achieve better performance. Yim et al. regarded the relationship between features from two layers in the teacher network as a novel knowledge and introduced the FSP (Flow of Solution Procedure) matrix to transfer this kind of information to the student network.

Nevertheless, the compressed networks using these algorithms still contain massive multiplications, which costs enormous computation resources. As a result, subtractions or additions are of much lower computational complexities when compared with multiplications. However, they have not been widely investigated in deep neural networks, especially in the widely used convolutional networks. Therefore, we propose to minimize the numbers of multiplications in deep neural networks by replacing them with subtractions or additions.

Networks without Multiplication

where $S(\cdot,\cdot)$ is a pre-defined similarity measure. If cross-correlation is taken as the metric of distance, i.e. $S(x,y)=x\times y$, Eq. (1) becomes the convolution operation. Eq. (1) can also implies the calculation of a fully-connected layer when $d=1$. In fact, there are many other metrics to measure the distance between the filter and the input feature. However, most of these metrics involve multiplications, which bring in more computational cost than additions.

2 Optimization

Neural networks utilize back-propagation to compute the gradients of filters and stochastic gradient descent to update the parameters. In CNNs, the partial derivative of output features $Y$ with respect to the filters $F$ is calculated as:

where $i\in[m,m+d]$ and $j\in[n,n+d]$. To achieve a better update of the parameters, it is necessary to derive informative gradients for SGD. In AdderNets, the partial derivative of $Y$ with respect to the filters $F$ is:

where $\mbox{sgn}(\cdot)$ denotes the sign function and the value of the gradient can only take +1, 0, or -1.

Besides the gradient of the filters, the gradient of the input features $X$ is also important for the update of parameters. Therefore, we also use the full-precision gradient (Eq. (5)) to calculate the gradient of $X$. However, the magnitude of the full-precision gradient may be larger than +1 or -1. Denote the filters and inputs in layer $i$ as $F_{i}$ and $X_{i}$. Different from $\frac{\partial Y}{\partial F_{i}}$ which only affects the gradient of $F_{i}$ itself, the change of $\frac{\partial Y}{\partial X_{i}}$ would influence the gradient in not only layer $i$ but also layers before layer $i$ according to the gradient chain rule. If we use the full-precision gradient instead of the sign gradient of $\frac{\partial Y}{\partial X}$ for each layer, the magnitude of the gradient in the layers before this layer would be increased, and the discrepancy brought by using full-precision gradient would be magnified. To this end, we clip the gradient of $X$ to $$to prevent gradients from exploding. Then the partial derivative of output features$Y$with respect to the input features$X$ is calculated as:

where $\mbox{HT}(\cdot)$ denotes the HardTanh function:

3 Adaptive Learning Rate Scaling

In conventional CNNs, assuming that the weights and the input features are independent and identically distributed following normal distribution, the variance of the output can be roughly estimated as:

If variance of the weight is $Var[F]=\frac{1}{d^{2}c_{in}}$, the variance of output would be consistent with that of the input, which will be beneficial for the information flow in the neural network. In contrast, for AdderNets, the variance of the output can be approximated as:

when $F$ and $X$ follow normal distributions. In practice, the variance of weights $Var[F]$ is usually very small , e.g. $10^{-3}$ or $10^{-4}$ in an ordinary CNN. Hence, compared with multiplying $Var[X]$ with a small value in Eq. (8), the addition operation in Eq. (9) tends to bring in a much larger variance of outputs in AdderNets.

We next proceed to show the influence of this larger variance of outputs on the update of AdderNets. To promote the effectiveness of activation functions, we introduce batch normalization after each adder layer. Given input $x$ over a mini-batch $\mathcal{B}=\left\{x_{1},\cdots,x_{m}\right\}$, the batch normalization layer can be denoted as:

Given a much larger variance $Var[Y]=\sigma_{\mathcal{B}}$ in Eq. (9), the magnitude of the gradient w.r.t $X$ in AdderNets would be much smaller than that in CNNs according to Eq. (11), and then the magnitude of the gradient w.r.t the filters in AdderNets would be decreased as a result of gradient chain rule.

A straightforward idea is to directly adopt a larger learning rate for filters in AdderNets. However, it is worth noticing that the norm of gradient differs much in different layers of AdderNets as shown in Table 1, which requests special consideration of filters in different layers. To this end, we propose an adaptive learning rate for different layers in AdderNets. Specifically, the update for each adder layer $l$ is calculated by

where $\gamma$ is a global learning rate of the whole neural network (e.g. for adder and BN layers), $\Delta L(F_{l})$ is the gradient of the filter in layer $l$ and $\alpha_{l}$ is its corresponding local learning rate. As filters in AdderNets act subtraction with the inputs, the magnitude of filters and inputs are better to be similar to extract meaningful information from inputs. Because of the batch normalization layer, the magnitudes of inputs in different layers have been normalized, which then suggests a normalization for the magnitudes of filters in different layers. The local learning rate can therefore be defined as:

where $k$ denotes the number of elements in $F_{l}$, and $\eta$ is a hyper-parameter to control the learning rate of adder filters. By using the proposed adaptive learning rate scaling, the adder filters in different layers can be updated with nearly the same step. The training procedure of the proposed AdderNet is summarized in Algorithm 1.

Experiment

In this section, we implement experiments to validate the effectiveness of the proposed AdderNets on several benchmark datasets, including MNIST, CIFAR and ImageNet. Ablation study and visualization of features are provided to further investigate the proposed method. The experiments are conducted on NVIDIA Tesla V100 GPU in PyTorch.

To illustrate the effectiveness of the proposed AdderNets, we first train a LeNet-5-BN on the MNIST dataset. The images are resized to $32\times 32$ and are pro-precessed following . The networks are optimized using Nesterov Accelerated Gradient (NAG), and the weight decay and the momentum were set as $5\times 10^{-4}$ and 0.9, respectively. We train the networks for 50 epochs using the cosine learning rate decay with an initial learning rate 0.1. The batch size is set as 256. For the proposed AdderNets, we replace the convolutional filters in LeNet-5-BN with our adder filters. Note that the fully connected layer can be regarded as a convolutional layer, we also replace the multiplications in the fully connect layers with subtractions. We set the hyper-parameter in Eq. (13) to be $\eta=0.1$, which achieves best performance compared with other values from the pool $\left\{1,\frac{1}{2},\frac{1}{5},\frac{1}{10},\frac{1}{20}\right\}$.

The convolutional neural network achieves a $99.4\%$ accuracy with $\sim$435K multiplications and $\sim$435K additions. By replacing the multiplications in convolution with additions, the proposed AdderNet achieves a 99.4% accuracy, which is the same as that of CNNs, with $\sim$870K additions and almost no multiplication.In fact, the theoretical latency of multiplications in CPUs is also larger than that of additions and subtractions. There is an instruction table www.agner.org/optimize/instruction_tables.pdf which lists the instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs. For example, in VIA Nano 2000 series, the latency of float multiplication and addition is 4 and 2, respectively. The AdderNet using LeNet-5 model will have $\sim$1.7M latency while CNN will have $\sim$2.6M latency in this CPU. In conclusion, the AdderNet can achieve similar accuracy with CNN but have fewer computational cost and latency. Noted that CUDA and cuDNN optimized adder convolutions are not yet available, we do not compare the actual inference time.

2 Experiments on CIFAR

We then evaluate our method on the CIFAR dataset, which consist of $32\times 32$ pixel RGB color images. Since the binary networks can use the XNOR operations to replace multiplications, we also compare the results of binary neural networks (BNNs). We use the same data augmentation and pro-precessing in He et al. for training and testing. Following Zhou et al. , the learning rate is set to 0.1 in the beginning and then follows a polynomial learning rate schedule. The models are trained for 400 epochs with a 256 batch size. We follow the general setting in binary networks to set the first and last layers as full-precision convolutional layers. In AdderNets, we use the same setting for a fair comparison. The hyper-parameter $\eta$ is set to 0.1 following the experiments on the MNIST dataset.

The classification results are reported in Table 2. Since computational cost in batch normalization layer, the first layer and the last layer are significantly less than other layers, we omit these layers when counting FLOPs. We first evaluate the VGG-small model in the CIFAR-10 and CIFAR-100 dataset. As a result, the AdderNets achieve nearly the same results (93.72% in CIFAR-10 and 72.64% in CIFAR-100) with CNNs (93.80% in CIFAR-10 and 72.73% in CIFAR-100) with no multiplication. Although the model size of BNN is much smaller than those of AdderNet and CNN, its accuracies are much lower (89.80% in CIFAR-10 and 65.41% in CIFAR-100). We then turn to the widely used ResNet models (ResNet-20 and ResNet-32) to further investigate the performance of different networks. As for the ResNet-20, Tte convolutional neural networks achieve the highest accuracy (i.e. 92.25% in CIFAR-10 and 68.14% in CIFAR-100) but with a large number of multiplications (41.17M). The proposed AdderNets achieve a 91.84% accuracy in CIFAR-10 and a 67.60% accuracy in CIFAR-100 without multiplications, which is comparable with CNNs. In contrast, the BNNs only achieve 84.87% and 54.14% accuracies in CIFAR-10 and CIFAR-100. The results in ResNet-32 also suggest that the proposed AdderNets can achieve similar results with conventional CNNs.

3 Experiments on ImageNet

We next conduct experiments on the ImageNet dataset , which consist of $224\times 224$ pixel RGB color images. We use ResNet-18 model to evaluate the proposed AdderNets follow the same data augmentation and pro-precessing in He et al. . We train the AdderNets for 150 epochs utilizing the cosine learning rate decay . These networks are optimized using Nesterov Accelerated Gradient (NAG), and the weight decay and the momentum are set as $10^{-4}$ and 0.9, respectively. The batch size is set as 256 and the hyper-parameter in AdderNets is the same as that in CIFAR experiments.

Table 3 shows the classification results on the ImageNet dataset by exploiting different nerual networks. The convolutional neural network achieves a 69.8% top-1 accuracy and an 89.1% top-5 accuracy in ResNet-18. However, there are 1.8G multiplications in this model, which bring enormous computational complexity. Since the addition operation has smaller computational cost than multiplication, we propose AdderNets to replace the multiplications in CNNs with subtractions. As a result, our AdderNet achieve a 66.8% top-1 accuracy and an 87.4% top-5 accuracy in ResNet-18, which demonstrate the adder filters can extract useful information from images. Rastegari et al. proposed the XNOR-net to replace the multiplications in neural networks with XNOR operations. Although the BNN can achieve high speed-up and compression ratio, it achieves only a 51.2% top-1 accuracy and a 73.2% top-5 accuracy in ResNet-18, which is much lower than the proposed AdderNet. We then conduct experiments on a deeper architecture (ResNet-50). The BNN could only achieve a 55.8% top-1 accuracy and a 78.4% top-5 accuracy using ResNet-50. In contrast, the proposed AdderNets can achieve a 74.9% top-1 accuracy and a 91.7% top-5 accuracy, which is closed to that of CNN (76.2% top-1 accuracy and 92.9% top-5 accuracy).

4 Visualization Results

Visualization on filters. We visualize the filters of the LeNet-5-BN network in Figure 2. Although the AdderNets and CNNs utilize different distance metrics, filters of the proposed adder networks (see Figure 2 (a)) still share some similar patterns with convolution filters (see Figure 2 (b)). The visualization experiments further demonstrate that the filters of AdderNets can effectively extract useful information from the input images and features.

5 Ablation Study

We propose to use a full-precision gradient to update the filters in our adder filters and design an adaptive learning rate scaling for deal with different layers in AdderNets. It is essential to evaluate the effectiveness of these components. We first train the LeNet-5-BN without changing its learning rate, which results in 54.91% and 29.26% accuracies using full-precision gradient and sign gradient, respectively. The networks can be hardly trained since its gradients are very small. Therefore, it is necessary to increase the learning rate of adder filters.

We directly increase the learning rate for filters in AdderNets by 100, which achieves best performance with full-precision gradient compared with other values from the pool $\left\{10,50,100,200,500\right\}$. As shown in Figure 3, the AdderNets using adaptive learning rate (ALR) and increased learning rate (ILR) achieve 97.99% and 97.72% accuracy with sign gradient, which is much lower than the accuracy of CNN (99.40%). Therefore, we propose the full-precision gradient to precisely update the weights in AdderNets. As a result, the AdderNet with ILR achieves a 98.99% accuracy using the full-precision gradient. By using the adaptive learning rate (ALR), the AdderNet can achieve a 99.40% accuracy, which demonstrate the effectiveness of the proposed ALR method.

Impact of parameters. As discussed above, the proposed adaptive learning rate scaling has a hyper-parameter: $\eta$. We then test its impact on the accuracy of the student network by conducting the experiments on the MNIST dataset. We use LeNet-5-BN as the backbone of AdderNet. Other experimental settings are same as mentioned in Sec. 4.1. It can be seen from Table 4 that the AdderNets trained utilizing the adaptive learning rate scaling achieves the highest accuracy (99.40%) when $\eta$ = 0.1. Based on the above analysis, we keep the setting of hyper-parameters for the proposed method.

Conclusions

Acknowledgement

We thank anonymous reviewers for their helpful comments. This work is supported by National Natural Science Foundation of China under Grant No. 61876007, 61872012, National Key R&D Program of China (2019YFF0302902), Beijing Academy of Artificial Intelligence (BAAI), and Australian Research Council under Project DE-180101438.

References

Appendix A Convergence of Sign and Full-precision Gradient

The partial derivative of $Y$ with respect to the filters $F$ is:

where $\mbox{sgn}(\cdot)$ denotes the sign function and the value of the gradient can only take +1, 0, or -1. Since Eq. (15) almost never takes the direction of steepest descent and the direction only gets worse as dimensionality grows, we propose to use the full-precision gradient:

Given a fixed learning rate $\alpha$, this problem basically cannot converge to the optimal value using sign grad (Eq. ( 15)) via gradient descent.

The optimization problem 17 can be rewritten as:

where $x=\left\{x_{1},...,x_{n}\right\},f=\left\{f_{1},...,f_{n}\right\}$. The update of $f_{i}$ using gradient descent is:

where $f_{i}^{j}$ denotes the $f_{i}$ in $j$th iteration. Without loss of generality, we assume that $f_{i}^{0}<x_{i}$. So we have:

when $f_{i}^{j}<x_{i}$. Denote $t=\mbox{arg}\max_{j}f_{i}^{j}<x_{i}$, we have $f_{i}^{t+1}>=x_{i}$. If $f_{i}^{t+1}=f_{i}^{0}+(t+1)\alpha=x_{i}$ (i.e. $\frac{(x_{i}-f_{i}^{0})}{\alpha}=t+1$), $|f_{i}-x_{i}|$ can converge to the optimal value 0. However, if $f_{i}^{t+1}>x_{i}$, we have

Similarly, we have $f_{i}^{t+3}=f_{i}^{t+1}$. Therefore, the inequality holds:

The aim of filters is to find the most relevant part of input features, which meets the goal of Eq. (LABEL:optim). The $\alpha$ (i.e. the learning rate of neural networks) can be seen as fixed when using multi-step learning rate, which is widely used in the training. According to the Proposition 1, if we use the sign gradient, the AdderNets will achieve a poor performance.

For the optimization peoblem 17, $f$ can converge to the optimal value using full-precision gradient (Eq. (16)) with a fixed learning rate $\alpha$ via gradient descent when $\alpha<1$.

The optimization problem 17 can be rewritten as:

where $x=\left\{x_{1},...,x_{n}\right\},f=\left\{f_{1},...,f_{n}\right\}$. The update of $f_{i}$ using gradient descent is:

where $f_{i}^{j}$ denotes the $f_{i}$ in $j$th iteration. If $f_{i}^{j}<x_{i}$, then we have the inequality:

and $f_{i}^{j+1}<f_{i}^{j}$. Without loss of generality, we assume that $f_{i}^{0}<x_{i}$. Then $f_{i}^{j}$ is monotone and bounded with respect to $j$, so the limit of $f_{i}^{j}$ exists and $\lim_{j\to+\infty}f_{i}^{j}\leq x_{i}$. Assume that $\lim_{j\to+\infty}f_{i}^{j}=l<x_{i}$. For $\epsilon=\alpha(x_{i}-l)$, there exists $k$ subject to $l-f_{i}^{k}<\epsilon$. Then we have:

which is a contradiction. Therefore, $\lim_{j\to+\infty}f_{i}^{j}\geq x_{i}$. Finally, we have $\lim_{j\to+\infty}f_{i}^{j}=x_{i}$, i.e. $f$ can converge to the optimal value. ∎

Therefore, by utilizing the full-precision gradient, the filters can be updated precisely.