Binarising neural networks is a method to shorten the time they require to make a prediction. The method is elegant in that it does not add complexity to neural networks but instead takes it away. It turns out that binarisation also makes the inner workings of a neural network more intuitive.
This is the MNIST database [1]:
It is a collection of 70,000 28-by-28 pixel images featuring handwritten digits in 8-bit greyscale. The database contains images of each of the ten digits in roughly equal proportion. MNIST is unique in that it is the database on which new image classifiers tend to be tested and benchmarked. This reason is historical: The first successful implementation of an effective classifier using a neural network was tested on MNIST. The classifier achieved an unprecedented test error rate of 12.0% [2]. To compare to this early success, developers tend to benchmark their new classifiers on the MNIST database. A notable popular alternative to the MNIST database is the “Fashion MNIST” database, which features images of ten different kinds of fashion items [3].
Another fact that adds to the popularity of MNIST is its simplicity. It is intuitive to work with small images of handwritten digits belonging to one of only ten different categories. This simplicity is valuable since discussions of neural networks tend to be sophisticated and riddled with complexity and nuance. And often it is not an option to “dumb down” the discussion of those networks, for relevant detail would be lost. MNIST is then a perfect solution to explain complex algorithms, as one can track the exact modifications the images undergo on their way through the network.
And even if such tracking does not lead to a full understanding of the network, it certainly helps to develop an intuition for its inner workings, thereby making the “black box” approach of algorithms like neural networks slightly less black [4]. For this reason, the MNIST database lends itself to dispell confusion gathered around an arguably intuitive and demonstrably efficient type of neural network: Binarised Neural Networks.
Binarised Neural Networks
A binarised neural network (BNN) is in its structure identical to any other “classical” neural network. And this applies regardless of whether this “classical” neural network contains convolutions, recursions, gates or even more sophisticated elements. A BNN does differ from “classical” networks in that it questions one of their core assumption: Is it essential to perform all computations inside such networks with floating-point arithmetics? Is the precision afforded by floating-point arithmetics even necessary? Will a network stop being useful if one were to replace floating-point with bitwise arithmetics?
The idea is that bitwise operations are native to processors. Thus, by relying on bitwise rather than floating-point arithmetics, one can circumvent the computationally costly operations of multiplication and division [5]. Multiplications and divisions are intuitive for humans, but not for computers. Computers have to go to great length to imitate multiplications of floating-point values. So the idea is to make it easier for computers to calculate the output of a neural network. There is some nuance to replacing floating-point with bitwise instructions in algorithms like neural networks. Yet, the primary motivation of a BNN remains a simple one: Floating-point computations are costly, bitwise computations are not [6]. And the implication is simple as well: Thus, replacing floating-point with bitwise instructions promises to reduce a neural network execution time.
Using bitwise instructions requires to treat data stored inside neural networks as concatenations of individual bits. This binary treatment of data implies, for instance, implies that one stops interpreting the 8-bit colour value of one of the pixels in one of the MNIST images as either one of 256 different shades of grey. It implies that one treats the colour value as a string of 8 consecutive 0s and 1s. Or to put it differently: the 8 bits are treated like neurons in their own right, with values being either 0 or 1. A BNN does not recognise any data type different from individual bits. This restriction to individual bits shuts the door to typical colour value reinterpretations as unsigned characters (values 0 to 255) or floating-point (values between -1.0 to 1.0, for instance). It is easy to see how binarised neural networks came to their name.
The demonstration works as follows: First, TensorFlow [7] is used to construct a simple one-layer neural network with 10 output nodes and no activation function (a linear classifier). That is the same network architecture used by LeCun to achieve a test error rate of 12.0% on the MNIST database. The network is trained using 60,000 of the 70,000 MNIST images. It is tested on the remaining 10,000 images and run on a BeagleBone Black [8]. Then the network is binarised into a BNN and retrained according to the instructions laid about by Courbariaux and colleagues [5]. The training protocol for the binarised network is recorded in the Appendix. Measuring the processing time and test error rate yields these results:
| Floating-Point | Bitwise | |
| Input Layer Size (Bytes) | 784 | 784 |
| Input Layer Dimensions | 28 x 28 | 28 x 28 x 8 |
| Number of Trainable Weights & Biases | 794 | 6282 |
| Execution Time (Seconds) | 20.2 | 2.8 |
| Testing Error Rate | 12.6% | 11.3% |
Binarisation reduces the processing time by a factor of 7 while leaving the testing error at roughly the same rate. This observation is in line with [5], where the authors also report a reduction by a factor of 7. This result is a clear indication that binarisation speeds up neural networks all the leaving the test error rate unchanged. Binarisation has a further advantage, in that it enables one to peek inside a network and understand what it has learned to do. The linear classifier used in this demonstration is an apt demonstration for this clarifying effect of binarisation.
Linear Classifiers
Linear classifiers are the simplest form of neural networks. They contain only the bare minimum of elements that taken together can be called a neural network. Consider a linear classifier that tests whether a given MNIST image shows the digit 6. Such classifier is in essence little more than a collection of 784 floating-point values (the weights) and a recipe of how to use them. They are used by multiplying them with the 784 floating-point values that are the input image. The sum of those products make up the internal field and encodes the degree to which the classifier is confident that the input image does show the digit 6. A larger the internal field encodes larger certainty, a smaller internal field smaller certainty. If represented as a sketch, the classifier would look something like this:
It is easy to see why those 784 floating-point numbers are called weights. The workings of a linear classifier resemble this of a weighted linear regression [9], a statistical model where each weight assigns a degree of importance to its corresponding input value. In this light, the process of training a network is little more assigning varying degrees of relevance to different parts of the input image. In this picture of a linear classifier, the regression offset (the bias) finds no mention. In this discussion of BNNs, including the regression offset adds little to the understanding and is therefore consciously omitted. In practice, however, one is well advised to include one.
The single weighted linear regression computes a single internal field to determine how likely it is that the input shows, in this case, the number 6. By adding another nine weighted linear regressions with differently adjusted weights, the network is complete in its ability to predict whether the input image shows one of the ten digits. It is said to have a fully connected layer with ten output nodes. With ten simultaneously executed linear classifiers, the network would look like this:
The difficulty with relying on weighted regressions is in understanding what precisely those weights express. The regression (and neural networks, by extension) are working – but why? This lack of understanding presents something of a difficulty when one tries to improve the technology. After all, if one does not understand how many layers it takes to correctly and confidently separate one number from another and why, then one is left with more or less educated guesses. It appears that the engineering problem of classifying images has birthed a fundamental research question.
Unfortunately, there is little intuition about which mathematical principle or operation a trained set of weights encodes. Merely glancing at two sets of 784 floating-point numbers offers little insight why one set of numbers is adjusted to identify images showing the digit 3, while the other one does the same for the digit 7. There is some explanation invoking statistical momenta, which does involve a rather longish mathematical treatment [9]. However, it is hard to rid oneself of the feeling that the maths serves more the role of an explanatory crutch for missing intuition.
It appears that binarisation does help to develop this intuition. And the binarised version of the linear classifier helps to show how it does that.
Inside Binarised Networks
The way to binarise neural networks is to follow the recipe laid out in- Treat every bit in a network as a node of its own
- Replace all multiplications with bitwise XOR operations
- Replace all summations with bit counting
- Declare internal fields to be the number of 1-bits contained in all input nodes
In general, there is more nuance to those instructions. More sophisticated binarisation is required if the network contains elements like activation functions, convolutions or recurrences. For a linear classifier, however, this recipe is sufficient. It changes the previously introduced sketch of the linear classifier to something more like this:
Note, that the input layer now has an additional dimension of depth of size 8. Since a BNN treats each bit as a node of its own, the 8-bit colour information no longer encodes one of 256 different shades of grey. The colour information now represents 8 individual nodes in their own right, thus adding a dimension of depth. Also, it appears somewhat counterintuitive that a refusal to encode the colour information should somehow clarify the network’s inner workings. After all, giving up the notion that colour is a concatenation of 8 consecutive bits does little more than remove a helpful interpretation of an otherwise meaningless string of bits. Yet, it hopefully becomes clear that the bitwise interpretation of the data is, in fact, the more intuitive one.
A binarised linear classifier expresses its level of confidence in the number of 1-bits present in the XOR-modified input. For instance, a classifier trained to detect the digit 6 produces an XOR-modified input that is essentially “white” (all bits are set to 1), given that the input does show the digit 6. Thus, if the sequence of bits 10100111 were to represent one of 784 pixels the input 6, then the weights ???????? of an ideal classifier would satisfy the equation
10100111
^
????????
=
11111111
with the solution ???????? = 01011000. It becomes clear that ideally tuned weights are but the inverse input data. Such weights guarantee that the number of produced 1-bits after applying XOR is maximised. This approach to classification is elegant in that the same input image is unlikely to be classified as, say, digit 3. The following sketch perhaps highlights this mechanism:
The trained weights of the aforementioned binarised linear classifer seem to corroborate this interpretation. If depicted as images, the trained weights of classifier look like this:
| 0 | 1 | 2 | 3 | 4 |
|
|
|
|
|
| 5 | 6 | 7 | 8 | 9 |
|
|
|
|
|
None of the ten images shows a perfect inverse digit. But it does become clear that each image shows a kind of average of the handwritten inverse digits. One can perhaps spot this most easily in the weight images for the digits 0, 1 and 7. Coincidentally, those are the digits with the smallest test error rate (see Appendix).
The weight images are not perfect inverses of digits they are supposed to detect. Yet they are close to enough such that one can confidently say that the inverse-image-interpretation appears to explain one of the rules the weights have learned to encode. And one can point to those learned rules without needing to invoke maths or hand-waving explanations. One only needs to show pictures to make the point.
References
- [1] Yann LeCun, Corinna Cortes, Christopher J.C. Burges
- The MNIST Database
- Accessed: 2020-02-02
- http://yann.lecun.com/exdb/mnist/
- [2] Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner
- Gradient-based learning applied to document recognition
- Proceedings of the IEEE. 1998 Nov;86(11):2278-324
- https://ieeexplore.ieee.org/abstract/document/726791
- [3] Han Xiao, Kashif Rasul, Roland Vollgraf
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- arXiv preprint arXiv:1708.07747. 2017 Aug 25
- https://arxiv.org/abs/1708.07747
- [4] Davide Castelvecchi
- Can we open the black box of AI?
- Nature News. 2016 Oct 6;538(7623):20
- https://www.nature.com/news/can-we-open-the-black-box-of-ai-1.20731
- [5] Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El-Yaniv, Yoshua Bengio
- Binarized neural networks: Training deep neural networks with weights and activations constrained to +1 or -1
- arXiv preprint arXiv:1602.02830. 2016 Feb 9
- https://arxiv.org/abs/1602.02830
- [6] Minje Kim, Paris Smaragdis
- Bitwise neural networks
- arXiv preprint arXiv:1601.06071. 2016 Jan 22.
- https://arxiv.org/abs/1601.06071
- [7] Martín Abadi et al.
- TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems
- TensorFlow Whitepaper
- https://www.tensorflow.org/
- [8] beagleboard.org Foundation
- BeagleBone Black
- BeagleBone Black Specifications
- https://beagleboard.org/black/
- [9] Tilo Strutz
- Data Fitting and Uncertainty: A Practical Introduction to Weighted Least Squares and Beyond
- ISBN: 978-3-658-11455-8
- https://www.google.com/search?tbm=bks&q=isbn:9783658114558
Appendix
Binarised Linear Classifier Training Protocol
The following images show both the test error rate and the confusion matrix. The lighter blue a diagonal element appears, the more images of the corresponding label have been correctly classified. Conversely, the lighter blue an off-diagonal element appears, the more images of the corresponding label have been misclassified.
Move the slider beneath the confusion matrix image to view the matrix at different stages during the first 100 training epochs.
0 Comments