SiMaN: Sign-to-Magnitude Network Binarization

To achieve high-quality weight binarization, different from the conference version [24], we reformulate the learning objective in Eq. (3) as

where $|\cdot|$ returns the absolute result of its input.

As can be seen, our learning objective is also built on the basis of angle alignment. Nevertheless, our method differs from Eq. (3) in many aspects: First, we drop the sign function since variables in a binarized network must be retained in a discrete set; thus, the binarization should be built upon the concept of the discrete optimization rather than the simple sign function. Second, we encode the weights into $\bar{\mathbf{b}}_{w}\in\{0,+1\}^{n}$ rather than $\mathbf{b}_{w}\in\{-1,+1\}^{n}$. In Corollary 1, we show that $\bar{\mathbf{b}}_{w}\in\{0,+1\}^{n}$ allows us to find an analytical solution in an efficient manner by transferring the high-magnitude weights to $+1$s and $0$s otherwise. Third, our angle alignment is independent of the rotation matrix, $\mathbf{R}$, since we remove the sign function, which makes the rotation direction unpredictable. Lastly, we align the angle difference between the binarization and absolute weight vector, $|\mathbf{w}|$, instead of the weight $\mathbf{w}$ itself. The rationale behind this is that our binarization falls into the non-negative set $\bar{\mathbf{b}}_{w}$. Fig. 2(b) outlines our binarization process.

Note that $\big{\|}|\mathbf{w}|\big{\|}_{2}$ is irrelevant to the optimization of Eq. (13). Thus, the learning can be simplified to

This is an integer programming problem [58]. Nevertheless, as demonstrated in Corollary 1, by learning the encoding space in $\{0,+1\}^{n}$, we can reach the global maximum in a substantially efficient fashion.

Corollary 1. For Eq. (14), the computational complexity of finding the global optimum is $\mathcal{O}(n\log{n})$.

Proof: For $\bar{\mathbf{b}}_{w}\in\{0,+1\}^{n}$, it is intuitive to see that $\|\bar{\mathbf{b}}_{w}\|_{2}$ falls into the set $\{\sqrt{1},...,\sqrt{n}\}$. Considering that $\|\bar{\mathbf{b}}_{w}\|_{2}=\sqrt{k}$ ($k=1,...,n$), the integer programming problem in Eq. (14) can be maximized by encoding to $+1$s those elements of $\bar{\mathbf{b}}_{w}$ that correspond to the largest $k$ entries of $|\mathbf{w}|$. To this end, we need to perform sorting upon $|\mathbf{w}|$, for which the complexity is $\mathcal{O}(n\log{n})$. Since $k$ has $n$ possible values, we need to evaluate Eq. (14) $n$ times, and then select the $\bar{\mathbf{b}}_{w}$ that maximizes the objective function, leading to a linear complexity with $n$. Hence, the overall complexity is $\mathcal{O}(n\log{n})$. $\hfill\blacksquare$

Therefore, given one filter weight $\mathbf{w}\in\mathbb{R}^{n}$, we can find the binarization $\bar{\mathbf{b}}_{w}\in\{0,+1\}^{n}$ having the smallest angle with $|\mathbf{w}|$. Note that $\bar{\mathbf{b}}_{w}$ found in this way is the global optimum. Furthermore, we emphasize that the proof of Corollary 1 indicates that the binarization in our framework involves the magnitudes of weights instead of the signs of weights, which significantly differentiates our work from existing works. In the next two sections, we show that the overall complexity can be further reduced to $\mathcal{O}(n)$, given the bit entropy maximization.

The capacity of a binarization model, often measured by the bit entropy, is maximized when it is half-half distributed, i.e., one half of the weights are encoded into $0$ and the other half are encoded into $+1$ [24, 29]. In this case, we expect to maximize our objective in Eq. (14) when those weights with the top-half magnitudes are encoded into $+1$s and the remaining are encoded into $0$s. However, we reveal that it is difficult to binarize $\mathbf{w}$ with entropy maximization due to its specific form of distribution.

Specifically, after training, $w\in\mathbf{w}$ is widely believed to roughly obey a zero-mean Laplacian distribution, i.e., $w\sim La(0,b)$, or a zero-mean Gaussian distribution, i.e., $w\sim\mathcal{N}(0,\sigma^{2})$ [22, 59, 60]. In Corollary 2, for the first time, we demonstrate its specific distribution.

Corollary 2. $w\in\mathbf{w}$ roughly follows a zero-mean Laplacian distribution.

Proof: Suppose $w$ is encoded into $+1$ if $|w|>t$, and 0 otherwise. Note that the learning of Eq. (14) can actually be regarded as a problem of finding the centroid of a subset [61] as well. Consequently, the learning process can be calculated by the integral as

where $f(w)$ represents the probability density function with regard to $w$. Then, we denote $p_{+1}$ as the proportion of $\mathbf{w}$ being encoded into $+1$s. Intuitively, its calculation can be derived as

To demonstrate our corollary, we first derive the theoretical values of $p_{+1}$ when $p(w)$ follows a Laplacian or Gaussian distribution, and then experimentally complete our final proof.

Laplacian distribution. In this case, we have $f(w)=\frac{1}{2b}e^{-w/b}$. Therefore, Eq. (15) becomes

Setting $\frac{\partial(b+t)\sqrt{e^{-t/b}}}{\partial t}=0$ to attain the maximum of Eq. (17), we have $t=b$. The proportion of $+1$s can be obtained as

Gaussian distribution. In this case, we have $f(w)=\frac{1}{\sqrt{2\pi}\sigma}e^{-w^{2}/(2\sigma^{2})}$. Similarly, Eq. (15) can be rewritten as

where $\operatorname{erfc}(\cdot)$ represents the well-known complementary error function [62].

Let $m=\frac{t}{\sqrt{2}\sigma}$, then Eq. (19) can be written as

Setting $\frac{\partial e^{-m^{2}}/\sqrt{\operatorname{erfc}(m)}}{\partial m}=0$, we have $m=\frac{t}{\sqrt{2}\sigma}\approx 0.43$. Thus, we obtain $t\approx 0.43\sqrt{2}\sigma$, and then derive the proportion of $+1$s:

As mentioned above, the trained weight $w\in\mathbf{w}$ obeys either a Laplacian distribution (with $p_{+1}\approx 0.37$) or a Gaussian distribution (with $p_{+1}\approx 0.54$). In Fig. 4(a), we conduct an experiment which shows a practical $p_{+1}$ of around 0.36$\sim$0.38 after training.¹¹1Similar phenomena can be observed in other layers and networks as well. This implies that $w\in\mathbf{w}$ follows a Laplacian distribution, and then our proof is completed. $\hfill\blacksquare$

The proof of Corollary 1 indicates that the binarization in our framework is related to the weight magnitude, i.e., $|\mathbf{w}|$. However, the Laplacian distribution contradicts the entropy maximization. To solve this, one naive solution is to assign the top half of elements of the sorted $|\mathbf{w}|$ with $+1$ and assign the remaining elements with $0$, that is

Despite helping achieve entropy maximization, such a simple operation violates the learning objective of minimizing the angular bias in Eq. (14) since $\tilde{\mathbf{b}}_{w}$ deviates significantly from the optimal $\bar{\mathbf{b}}_{w}$ as revealed in Corollary 3.

Corollary 3. Suppose $\bar{\mathbf{b}}_{w}$ is a binarized vector with a total of $k$ $+1$s and the binarized vector $\tilde{\mathbf{b}}_{w}$ has $r$ different bits from $\bar{\mathbf{b}}_{w}$. Then the angle between $\bar{\mathbf{b}}_{w}$ and $\tilde{\mathbf{b}}_{w}$ is bounded by $\big{[}\arccos\sqrt{\frac{k}{k+r}},\arccos\sqrt{\frac{k-r}{k}}\big{]}$.

Proof: To find the lower bound, we need to obtain $\tilde{\mathbf{b}}_{w}$ such that $\frac{(\bar{\mathbf{b}}_{w})^{T}\tilde{\mathbf{b}}_{w}}{\|\bar{\mathbf{b}}_{w}\|_{2}\|\tilde{\mathbf{b}}_{w}\|_{2}}$ is maximized. Intuitively, this can be achieved when $\tilde{\mathbf{b}}_{w}$ has all ones at the same positions as $\bar{\mathbf{b}}_{w}$, and $r$ additional ones in the remaining positions, in which $\|\tilde{\mathbf{b}}_{w}\|_{2}=\sqrt{k+r}$ and $(\bar{\mathbf{b}}_{w})^{T}\tilde{\mathbf{b}}_{w}=k$. Then, we have the lower bound of $\arccos\sqrt{\frac{k}{k+r}}$. To obtain the upper bound, we need to minimize $\frac{(\bar{\mathbf{b}}_{w})^{T}\tilde{\mathbf{b}}_{w}}{\|\bar{\mathbf{b}}_{w}\|_{2}\|\tilde{\mathbf{b}}_{w}\|_{2}}$, which can be done when there are ($k-r$) $+1$s in $\tilde{\mathbf{b}}_{w}$ in the common positions with $\bar{\mathbf{b}}_{w}$ and the rest are set to zeros. In this case, we have $\|\tilde{\mathbf{b}}\|_{2}=\sqrt{k-r}$ and $(\bar{\mathbf{b}}_{w})^{T}\tilde{\mathbf{b}}_{w}=k-r$, which leads to the upper bound of $\arccos\sqrt{\frac{k-r}{k}}$.

According to Corollary 2 and Eq. (22), we have $k\approx 0.37n$, and $r\approx 0.13n$. Then, we can derive the practical angle bounds as $[\arccos\sqrt{\frac{0.37}{0.37+0.13}},\arccos\sqrt{\frac{0.37-0.13}{0.37}}]\approx[30.66^{\circ},36.35^{\circ}]$. Therefore, a large angle bias occurs between the solution $\tilde{\mathbf{b}}_{w}$ from Eq. (22) and the solution $\bar{\mathbf{b}}_{w}$ from optimizing Eq. (14). In Sec. 5.2, we demonstrate the poor performance when simply using $\tilde{\mathbf{b}}_{w}$.

Instead of imposing an additional loss term to regularize the ideal half-half binarization, we analyze the numerical value of each weight and reveal that simply removing the $\ell_{2}$ regularization can explicitly maximize the bit capacity, leading to a more informative binarized network.

Let $\mathcal{L}^{k}_{\mathbf{b}_{w}}=\mathop{\arg\max}_{\mathbf{b}_{w}}\frac{(\mathbf{b}_{w})^{T}}{\sqrt{k}}|\mathbf{w}|=\frac{\sum_{i=1}^{k}\tilde{w}_{i}}{\sqrt{k}}$ denote the maximum result of the integer programming problem in Eq. (14), where $\tilde{w}_{i}\in|\mathbf{w}|$ corresponds to the $i$-th largest magnitude. We have $\mathcal{L}^{k+1}_{\mathbf{b}_{w}}<\mathcal{L}^{k}_{\mathbf{b}_{w}}$, i.e.,

We can deduce that

For Laplacian distributed weights, we know that $k\approx 0.37n$. Thus, the above inequality can be rewritten as

Since $n$ is typically thousands for a neural network and we statistically find that $\mathcal{L}^{k}_{\mathbf{b}_{w}}$ ranges from 0.63 to 0.73, the multiplication of the two terms in Eq. (25) thus results in an extremely small $\tilde{w}_{k+1}$ approximating to zero. Thus, we need to enlarge the value of $\tilde{w}_{k+1}$ to break the above inequality. We realize that one of the major causes for a small $\tilde{w}_{k+1}$ lies in the existence of the $\ell_{2}$ regularization imposed on the training of neural network. This inspires us to remove the $\ell_{2}$ regularization for the to-be-binarized weights $\mathbf{w}$.

As shown in Fig. 4(b), the removal of the $\ell_{2}$ regularization increases the proportion of $+1$s in $\bar{\mathbf{b}}_{w}$ to around 0.50$\sim$0.52. Taking 0.51 as an example, we then further enforce the ideal half-half binarization $\tilde{\mathbf{b}}_{w}$ using Eq. (22). As a result, $k\approx 0.51n$ and $r\approx 0.01n$, yielding the much smaller angle bounds of $[\arccos\sqrt{\frac{0.51}{0.51+0.01}},\arccos\sqrt{\frac{0.51-0.01}{0.51}}]\approx[7.97^{\circ},8.05^{\circ}]$ between $\tilde{\mathbf{b}}_{w}$ and $\bar{\mathbf{b}}_{w}$. This effectively increases the bit entropy and leads to a nearly optimal solution for the learning objective of Eq. (14). Besides, the half-half binarization further reduces the computational complexity of $\mathcal{O}(n\log n)$ to $\mathcal{O}(n)$ since we only need to find the median of $|\mathbf{w}|$, and encode weights into $+1$s when their magnitude is larger than the median, and 0s otherwise.

The forward and backward processes of SiMaN are summarized in Algorithm 1. During training, we remove the $\ell_{2}$ regularization and adopt the binarization $\mathbf{b}_{w}\in\{-1,+1\}^{n}$ transformed from the half-half binarization $\tilde{\mathbf{b}}_{w}\in\{0,+1\}^{n}$ for the convolution in Eq. (5). After training, we obtain a network consisting of a binarized weight $\tilde{\mathbf{b}}_{w}$ for practical deployment on hardware where the convolution is executed using the XNOR and bitcount operations in Eq. (12).

CIFAR-10 [34] consists of $60,000$ $32\times 32$ images from $10$ classes. Each class has $6,000$ images. We split the dataset into $50,000$ training images and $10,000$ testing images. Data augmentation includes random cropping and random flipping, as done in [1] for the training images.

ImageNet [26] contains over $1.2$ million images for training and $50,000$ validation images from $1,000$ classes for classification. For fair comparison with the recent advances in [29, 23, 24], we only apply the data augmentation including random cropping and flipping.

Network Structures For CIFAR-10, we binarize ResNet-18/20 [1] and VGG-small [67]. For ImageNet, ResNet-18/34 are chosen for binarization. Following [29, 23, 24], double skip connections [28] are added to the ResNets and we do not binarize the first and last layers for all networks.

Implementation Details We implement our SiMaN using Pytorch [68] and all experiments are conducted on NVIDIA Tesla V100 GPUs. We use the cosine scheduler with a learning rate of $0.1$ [29, 24]. The SGD is adopted as the optimizer with a momentum of $0.9$. For those layers that are not binarized, the weight decay is set to $5\times 10^{-4}$ on CIFAR-10 and $1\times 10^{-4}$ on ImageNet, and $0$ otherwise to remove the $\ell_{2}$ regularization for the bit entropy maximization as discussed in Sec. 4.3. We train the models from scratch with $400$ epochs and a batch size of $256$ on CIFAR-10, and with $150$ epochs and a batch size of $512$ on ImageNet.

Note that, we only apply the classification loss during network training for fair comparison. Other training losses such as those proposed in [69, 53, 70], the variants of network structures in [71, 72, 55], and even the two-step training strategy [33] can be integrated to further boost the binarized networks’ performance. These, however, are not considered here. We aim to show the advantages of our magnitude-based optimization solution over the traditional sign-based methods under regular training loss, the same network structure and a common training strategy.

In this subsection, we conduct ablation studies of different variants to demonstrate the efficacy of our SiMaN, as well as quantization error to demonstrate the superiority of our analytical discrete optimization.

SiMaN Variants. Our SiMaN is built by removing the $\ell_{2}$ regularization and enforcing the half-half strategy in Eq. (22). To analyze their influence, in Table I, we develop three variants, including (1) SiMaN₁: The $\ell_{2}$ regularization is added while removing the half-half binarization. This variant simply implements binarization based on the proof process of Corollary 1. It results in around $37\%$ of weights encoded into $+1$s, as analyzed in Corollary 2, which fails to maximize the entropy information, and thus leads to poorer accuracies of 55.1% for the top-1 and 75.5% for the top-5. (2) SiMaN₂: Both the $\ell_{2}$ regularization and the half-half binarization are removed. It shows better top-1 ($57.3\%$) and top-5 ($77.4\%$) accuracies since the removal of the $\ell_{2}$ regularization breaks the Laplacian distribution and results in around $51\%$ of weights being encoded into $+1$s as experimentally verified in Fig. 4. (3) SiMaN₃: Both the $\ell_{2}$ regularization and the half-half binarization are added. Though the performance increases, it is still limited. This is because, the half-half binarization with the $\ell_{2}$ regularization causes a large angle deviation of around $30.66^{\circ}-36.35^{\circ}$ as analyzed in Sec. 4.3, from the optimal binarization of our learning objective in Eq. (14).

Based on SiMaN₃, our SiMaN further removes the $\ell_{2}$ regularization. On one hand, this ensures the maximal bit entropy; on the other hand, it ensures that the half-half binarization closely matches the optimal binarization (only $7.97^{\circ}-8.05^{\circ}$ angle deviation as analyzed in Sec. 4.3), thereby leading to the best performance in Table I.

Quantization Error. Recall in Sec. 1, to mitigate the quantization error, XNOR-Net [25] compensates for the norm gap between the full-precision weight and the corresponding binarization. Our conference implementation of RBNN [24] introduces a rotation matrix to reduce the angular bias. In this paper, we reformulate the angle alignment objective and derive an analytical discrete solution. To validate the theoretical claims on reducing quantization error, we measure the practical quantization errors across different layers of ResNet-20 as a toy example in Fig. 5. Similar observations can be found in other networks as well.

In Fig. 5(1), we first measure the cosine similarity between the full-precision weight vector and the corresponding binarization. We can see that our earlier implementation of RBNN achieves a significantly higher cosine similarity than XNOR-Net does, implying fewer angular bias. Upon RBNN, our SiMaN further increases the cosine similarity across different network layers. Consequently, in Fig. 5(2), though XNOR-Net mitigates quantization error from the norm gap, quantization error still heavily accumulates in most layers since the angular bias remains unsolved. By weight rotation, our conference version of RBNN greatly closes the angular bias thus it can effectively decrease quantization error. Nevertheless, the alternating optimization in RBNN leads to sub-optimal binarization. Therefore, the quantization error in top layers still stays in a relatively large state. By contrast, the analytical optimization in SiMaN enables to further reduce the quantization error to a very small level, providing one new perspective of BNN optimization.

We further show the convergence ability of our SiMaN, and compare with its conference version of RBNN which implements network binarization with the sign function [24]. The experiments in Fig. 6 show that our sign-to-magnitude weight binarization has a significantly better ability to converge during BNN training than the traditional sign-based optimization on both training and validation sets, which demonstrates the feasibility of our discrete solution in learning BNNs.

We first conduct detailed studies on CIFAR-10 for the proposed SiMaN as shown in Table II. Despite that RBNN performs best in binarizing ResNet-20, our sign-to-magnitude binarization consistently outperforms the recent sign-based state-of-the-arts. Specifically, SiMaN outperforms RBNN [24] and SLB [65] by $0.3\%$ and $0.5\%$ in binarizing ResNet-18 and VGG-small, respectively. The results emphasize the importance of building discrete optimization to pursue high-quality weight binarization. Importantly, compared with the conference version, i.e., RBNN, our SiMaN increases the performance to $92.5\%$ when binarizing VGG-small, leading to a performance gain of $1.2\%$. Besides, SiMaN also merits in its easy implementation, where the median of absolute weights acts as the boundary between $0$s and $+1$s to ensure the bit entropy maximization, while the angle alignment is also guaranteed, as analyzed in Sec. 4.3. In contrast, RBNN has to learn two complex rotation matrices and applies them in the beginning phase of each training epoch in order to reduce the angle bias. Note that, for ResNet-20, we realize that smaller quantization error (see Fig. 5) does not necessarily lead to better performance. This indicates that there may exist an unexplored optimal solution that is not related to the quantization error. Nevertheless, it has been widely accepted in literature that quantization error can improve the BNN performance in most cases, which has been demonstrated by the experimental results (except ResNet-20) in this paper as well. This paper also addresses the quantization error problem.

We also conduct similar experiments on ImageNet to validate the performance of SiMaN on a large-scale dataset. Two common networks, ResNet-18 and ResNet-34, are adopted for binarization. Table III shows the results of SiMaN and several other binarization methods. The performance of SiMaN on ImageNet also takes the leading place. Specifically, with ResNet-18, SiMaN achieves $60.1\%$ top-1 and $82.3\%$ top-5 accuracies, respectively, with $0.2\%$ and $0.4\%$ improvements over its conference version of RBNN. By doubling the number of residual blocks and shrinking per-block convolutions, ReActNet [55] achieves 65.9% top-1 accuracy. To manifest the advantage of our discrete optimization, we further perform SiMaN on the modified network structure and obtain a better performance of 66.1%. With ResNet-34, it achieves a top-1 accuracy of $63.9\%$ and a top-5 accuracy of $84.8\%$, outperforming RBNN by $0.8\%$ and $0.4\%$, respectively.

The performance improvements in Table II and Table III strongly demonstrate the impact of exploring discrete optimization and the effectiveness of our magnitude-based discrete solution in constructing a high-performing BNN.