Year: 2021

Abstract:
Modern image recognition models span millions of parameters occupying several megabytes and sometimes gigabytes of space, making it difficult to run on resource constrained edge hardware. Binary Neural Networks address this problem by reducing the memory requirements (one single bit per weight and/or activation). The computation requirement and power consumption are also reduced accordingly. Nevertheless, in such networks, each neuron has a large number of inputs, making it difficult to implement them efficiently in binary hardware accelerators, especially LUT-based approaches. In this work, we present a pruning algorithm and associated results on convolutional and dense layers from aforementioned binary networks. We reduce the computation by 4-70x and the memory by 190-2200x with less than 2% loss of accuracy on MNIST and less than 3% loss of accuracy on CIFAR-10 compared to full precision, fully connected equivalents. Compared to very recent work on pruning for binary networks, we still have a gain of 1% on the precision and up to 30% reduction in memory (526KiB vs 750KiB).

heading: 1 INTRODUCTION
text: AI has become ubiquitous in our daily lives, be it the use of search engines to find information or automatically tagging photos on social media. While the predictive accuracy of these models have grown, the size and computation requirements have grown by several orders of magnitude or more, making AI a niche field where only few can participate. This practice is also proving to be environmentally unfriendly with Strubell et al. (2019) estimating the footprint of training an NLP model to be 626,000 pounds of carbon dioxide equivalent.
To counter this growing computation need, it is important to develop hardware accelerators which are easily re-configurable. A Field Programmable Gate Array (FPGA) is an integrated circuit designed to be reconfigured by the user and acts as a blank canvas for implementing custom circuits (in our case custom models). FPGAs embed millions of lookup tables (LUTs) that ”compute” (actually fetch) the output given the values of their binary inputs. The problem is that these LUTs are limited in size (typically 6-12 inputs) and using multiple LUTs per neuron is less efficient. This raises the need for both binarizing our weights (and/or activation) and reducing the number of inputs per neuron.
In Sections 2 and 3 we go through existing works on binarization and pruning of fully connected, full precision networks. In Section 4, we introduce iPrune, an effective way to prune the weights of binary networks. In Section 5, we compare the accuracy, memory and computation requirements of these network implementations against their full precision, fully connected equivalents. In Section 6, we report some intriguing results about a-priori pruning versus post-training pruning. Section 7 concludes this work.

heading: 2 BINARIZATION TECHNIQUES
text: Binarization is the process of converting the weights and/or activations to a 1-bit representation (±1) instead of the classic N-bit representation (typically 8-bit, 16-bit or 32-bit). This gives us a direct
memory saving of up to 32x. There are several approaches in literature on binarization. Throughout our experiments, we worked with BinaryConnect whose details are given in the next subsection.

heading: 2.1 BINARYCONNECT
text: Courbariaux et al. (2015) introduced BinaryConnect, the first paper of its kind, with details on binarization of both convolutional and dense weights. There are two sub-types based on how the binarization is performed.
• Deterministic: The weights are binarized deterministically; specifically, using the sign function on the hard-sigmoid of the weight.
• Stochastic: The weights are set to -1 with probability (1-σ(Wi)) and 1 with probability σ(Wi) where σ is the hard-sigmoid function.
The hard-sigmoid function mentioned above is given by:
σ(x) = clip
( x+ 1
2 , 0, 1
) (1)
During the back-propagation, the full precision weights are updated based on the gradient with respect to the binary weights. The pseudocode for BinaryConnect is given in Algorithm 1
Algorithm 1 Algorithm for BinaryConnect 1. Forward propagation:
wb ← binarize(wt−1) for k = 1 : L do
compute ak knowing ak−1, wb and bt−1 end for

heading: 2. Backward propagation
text: for k = L : 2 : −1 do
Compute ∂C∂ak−1 knowing ∂C ∂ak and wb end for

heading: 3. Parameter update
text: Compute ∂C∂wb and ∂C ∂bt−1
knowing ∂C∂ak and ak−1 wt ← clip(wt−1 − η ∂C∂wb ) bt ← bt−1 − η ∂C∂bt−1

heading: 3 PRUNING TECHNIQUES
text: Hoefler et al. (2021) discusses in detail different approaches to pruning and was used as a reference for our methods. The different types of pruning techniques are given in Figure 1. A few approaches are described in detail in Sections 3.1 and 3.2

heading: 3.1 STRUCTURE VS UNSTRUCTURED PRUNING
text: Structured pruning is the removal of neurons or weights in a structured fashion i.e. based on a fixed pattern. Common methods for structured pruning are neuron pruning (since this is just a row/column removed from the weight matrix) and filter/transformer head removal. Similarly, strided removal of weights after an offset is also an example of structured pruning.
On the other hand, unstructured pruning refers to the pruning method where there are no patterns in how the weights are removed. While this does not help with easier matrix calculation, it tends to provide higher baselines than structured pruning and can often be converted to structured pruning through a minor set of modifications.

heading: 3.2 MAGNITUDE PRUNING
text: It is a simple and effective selection scheme where the magnitude of the weights is used as a metric to determine which weights to drop and which weights to keep. After sparsifying the network this way, retraining is done to get high accuracies again.
There are three ways to perform magnitude pruning; globally, layer-wise or neuron-wise. Global magnitude pruning takes all weights from all layers and keeps the top-k weights among them. This often has the problem of vanishing gradients or even vanishing layers (because most weights have been removed from the layer). Figure 2 gives the distribution of weights before and after applying global magnitude pruning.
Layer-wise magnitude pruning (used in Guerra et al. (2020)) keeps the top-k weights across all neurons per layer and overcomes the issue of vanishing layers. This is still difficult to implement in LUTs, because some neurons will have a large number of connections while others will have very few after pruning.
Lastly, neuron-wise magnitude pruning keeps the top-k weights for each neuron. This overcomes both the issues of vanishing layers/gradients and LUT implementation, but often comes at the cost of low initial accuracy which can be solved by retraining the network. In all our experiments, we use neuron-wise magnitude pruning.

heading: 3.3 LOTTERY TICKET HYPOTHESIS
text: The Lottery Ticket Hypothesis initially introduced in Frankle & Carbin (2018), and extended to quantized networks in Diffenderfer & Kailkhura (2021) theorizes that there exists optimal subnetworks in the initialization of an overparameterized network. The authors prove theoretically and validate practically this claim in their papers. They introduce a learnable parameter ”score” which decide the weights to retain and the ones to drop. Diffenderfer & Kailkhura (2021) claims to reduce network sizes by 50% with negligible reduction or sometimes even increase in accuracy compared to the fully connected counterparts.

heading: 4 IPRUNE
text: iPrune is a magnitude based unstructured pruning technique to reduce the number of inputs to each neuron of a particular layer in a neural network.
For dense layers, the magnitude is computed and the top-k weights are chosen for each neuron of the current layers (top-k columns for each row in the weight matrix of shape (out features, in features)). For convolutions, the L1 norm across the kernel dimensions (kx, ky) is computed to reduce it to an (out channels, in channels) representation. This is then followed by pruning using top-k weights similar to the dense case.
Disconnecting neurons from previous layers can be easily accomplished in most deep-learning frameworks with the use of a mask. Neurons which remain connected have a mask value 1 and the others have 0. In Figure 3, for a given example mask and weight, the computation of the masked weight is shown. The figure also highlights the structure of the mask.
Algorithm 2 provides pseudocode for iPrune. Note that the update step, performed on the full precision weights uses the gradients with respect to the binary masked weights ( ∂C ∂wm ) .

heading: 5 EXPERIMENTAL RESULTS
text: We performed tests on MNIST (LeCun et al. (1998)) and CIFAR-10 (Krizhevsky & Hinton (2009)) datasets. For all the results given below, the network architecture used for MNIST was (1024D - 1024D - 10D) and for CIFAR-10 a modified version of VGGSmall, specifically: (128C3 - 128C3 - MP2 - 256C3 - 256C3 - MP2 - 512C3 -

heading: 512C3 - MP2 - 1024D - 1024D - 10D)
text: For MNIST, no preprocessing was performed. We skipped the last layer while pruning. For CIFAR10 we applied ZCA preprocessing as was suggested in Courbariaux et al. (2015) for gains of around 2-3% in accuracy. We applied weight-decay (5e-2) on the last layer (dense) of the network and used the square hinge loss as the loss function. This together behaves like an L2-SVM block. We use the Adam optimizer with initial learning rate of 3e-3 with no learning rate scheduler. While pruning, we skipped the first two convolution layers and the last dense layer.
Figure 4 shows the effect of iPrune on the weight values for the models we trained. Notice how the number of neurons with weight magnitude close to zero reduces in both cases. At the same time the
Algorithm 2 Algorithm for iPrune 0. Train a fully connected model 1. Compute the mask - Done only once
w.mask = find mask(w) 2. Forward propagation: wb ← binarize(w) wm = wb ∗ w.mask for k = 1 : L do
compute ak knowing ak−1, wm and b end for

heading: 3. Backward propagation
text: for k = L : 2 : −1 do
Compute ∂C∂ak−1 knowing ∂C ∂ak and wm end for

heading: 4. Parameter update
text: Compute ∂C∂wm and ∂C ∂b knowing ∂C ∂ak
, ak−1 and w.mask w ← clip(w − η ∂C∂wm ) b← b− η ∂C∂b
number of these weights is not zero as we are applying neuron wise pruning, not global pruning. Also note that in the BinaryConnect case, the original distribution is a mixture of three Gaussians centered at -1, +1 and 0 while in the FP case, there is only one Gaussian centered at 0.
Table 1 gives the results after applying iPrune on MNIST. There is less than 2.3% difference between the fully connected, full precision network and pruned BinaryConnect deterministic model with 7/8 inputs. The memory gain is around 2200x and computation gain is around 70x.
Table 2 gives the accuracy memory and computation requirement for different percentages of weights remaining per neuron. It is clear that we can reduce the memory by 1.9x-4.7x (remaining weights 50%-20%) and computation by 1.9x-4.4x, compared to the fully connected BinaryConnect deterministic network, with negligible loss in accuracy (less than 1%).
Since we observed in our early experiments with MNIST that dense layers can be pruned further, we performed a gridsearch with different percentages/number of weights remaining in convolution and dense layers. The results are given in Table 3. The baseline accuracy for these models is 87.64%. The results mostly show a trend of increasing accuracy with increasing number of dense/percentage of convolution weights per neuron apart from a few anomalies. We can also observe that the computation and memory requirements are highly skewed towards reduction in convolution parameters than dense parameters.
Also note, based on Table 2, Table 3, and our baseline accuracy for fully connected, full precision model (88.21%), that with less than 3% reduction in accuracy, we were able to save up to 180x in memory and up to 4.4x in computation.
Previous work on this topic (Guerra et al. (2020)), which used layer wise unstructured pruning, was able to prune BinaryConnect models to 750 KB size with 1.4x reduction in computation while our models with 1% higher accuracy can be pruned to as low as 526 KB with upto 3.1x reduction in computation. Compared to pruning full precision models from Li et al. (2016) we reduce memory by upto 41x (526KB vs 21.6 MB) with 6% reduction in accuracy (Note that the comparisons have been done with results of closest equivalent VGG models reported by the authors).

heading: 6 IPRUNE FOR RANDOMLY INITIALIZED NETWORKS
text: As an ablation study, we compared iPrune on a fully trained network for MNIST against iPrune on a randomly initialized network. Table 5 shows the results of iPrune on a randomly initialized network vs a fully trained network.
The idea behind this is that the initialization of networks greatly affects the magnitude of the gradient and subsequently the final value after training. Existing work on such ”Lottery Tickets” have been discussed in Section 3. Those methods use a learnable metric ”score” to determine the mask. This score is updated while training. Conversely, in this ablation, we compute the mask once, just after initialization, and assume that this is the ”Lottery Ticket” network. We allow the update of weights while training to allow the model to fit better to the data instead of updating the mask itself.
The results show that a randomly initialized network can be pruned to less than 1.5% reduction in accuracy for the same training parameters. This encourages further investigation in future works on larger models to validate our hypothesis. If this phenomenon is always observed, it can greatly help reduce the computation cost by removing the need to train larger models initially.

heading: 7 CONCLUSION AND FUTURE WORK
text: We were able to demonstrate pruning for binary neural networks and reduce the memory and computation requirement by more than 2200x and 70x on MNIST and 190x and 4.4x on CIFAR-10, respectively, compared to full precision, fully connected equivalents. Our CIFAR-10 results had 1% increase in accuracy but was only 70% of the size of the model from Guerra et al. (2020) with a reduction in computation time by 3.1x vs 1.4x in that paper.
The ability to prune randomly initialized neural networks and train to reasonably high accuracies is an interesting outcome and is worth investigating. Finally, extension of these algorithms for other forms of quantization (logarithmic, k-bit, etc.) would also be an interesting avenue for research.
We are also working on porting the trained weights to an FPGA to observe the gain in energy requirements and inference time. With such low number of inputs (fan in), we expect to be able to fit our neurons in lookup tables to further boost the performance.

Review summaries:
This paper combines two existing methods (i.e., binarization and pruning) to reduce both computational complexity and memory requirements of deep neural networks (DNNs). Binarryconnect method was exploited to binarize DNNs whereas neuron-wise magnitude pruning was used to remove unnecessary input activations. It was then shown that the combination of these two methods can significantly reduce both memory and computation on CIFAR-10 and MNIST datasets.