# Activation-Based Pruning of Neural Networks
## 3 Methodology
### Local Activation-Based Pruning  
The disadvantage of global activation-based pruning is the time and space complexity of the algorithm. Table 1 presents the time and space complexity for global and local activation-based pruning. We employed Big-\(\mathcal{O}\) notation as a standard means to express the time and space complexity of our proposed algorithm. For global activation-based  
Figure 1: Network before and after pruning. Values in the circles indicate the activation counter of the respective neurons.  
pruning, the space complexity for storing activation counters for \(n\) neurons is \(\mathcal{O}(n)\). Analyzing Algorithm 3, we find that the processing time for global activation-based pruning is \(\mathcal{O}(n\log(n))\). As the network grows larger, it puts a considerable strain on the memory and processing requirement for each pruning cycle. We present an alternative implementation for activation-based pruning, where pruning is performed on one hidden layer per pruning cycle. We obtain significant performance improvements if the total number of neurons in a single layer \(l\) is much less than the total number of neurons in the entire network \(n\), i.e., \(l\ll n\). The space complexity to store the activation counters is \(\mathcal{O}(l)\), and the time complexity for pruning is \(\mathcal{O}(l\log(l))\). We initiated pruning with the first hidden layer of the network immediately following the input layer. We sequentially applied this procedure to each subsequent hidden layer in the ensuing pruning cycles. We stopped after pruning the hidden layer before the output layer. If the total pruning of the network was set at \(x\%\), we pruned \(x\%\) of a hidden layer during one pruning cycle. The total number of pruning cycles is equal to the number of hidden layers present in the feedforward network. Algorithms 4-6 demonstrate the steps for pruning the network during training.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Pruning Type** & **Time** & **Space** \\ \hline Global & \(\mathcal{O}(n\log(n))\) & \(\mathcal{O}(n)\) \\ Local & \(\mathcal{O}(l\log(l))\) & \(\mathcal{O}(l)\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Time and space complexity for different types of pruning with \(l\ll n\), where \(n\) represents the total number of neurons in the hidden layers and \(l\) denotes the number of neurons in a single hidden layer.  
```
1:Input:\(l\): \(l\): hidden layer to be pruned,
2:Require:\(R_{l}\): list for activation counter and associated weights for layer \(l\), \(C_{p}\): current prune percentage, \(P_{index}\): prune index.
3:\(R_{l}\leftarrow(A_{l},W_{l})\). {assign activation counters and associated weights to \(R_{l}\)}.
4:if pruning type = neuron then
5: Sort \(R_{l}\) on the activation counter in ascending order.
6:else
7: Sort \(R_{l}\) on the product of the activation counter and weights in ascending order.
8:endif
9:\(P_{index}\gets C_{p}\times len(R_{l})\). {\(len(R_{l})\): No. of elements in \(R_{l}\)}.
10:\(R_{l_{W}}(0,P_{index})\gets 0\). {assign 0 value to weights}.
11:\(W_{l_{max}}\gets R_{l_{W}}\). {Set new weights for hidden layer \(l\)}.
12:return\(W_{l_{max}}\)
```  
**Algorithm 5** Update neuron.