Understanding Sub-Linear Deep Learning Engine
Anybody working in the field of ML/Data science is quite aptly aware of the increasing size of the models which ultimately increases the computing power required by these models both for training and inferencing. A general trend in the contemporary world of ML has been to either distribute the model or use specialized hardware called accelerators to achieve the desired computing power. The flip side of using accelerators is that these can be quite expensive.
There’s a lot of research going on to find ways to design better algorithms for training than developing specialized hardware. One such algorithm is called SLIDE (Sub-Linear Deep Learning Engine).
In this article, we’ll explore SLIDE in brief.
What is SLIDE?
Generally during model training, we parse the input through all the neurons, which triggers activation functions for each of them, and during backpropagation, we again update the weights for each of them.
The argument that this algorithm makes is that instead of activating each of the neurons there must be a way to find out which of the neurons are most likely to be activated by the current input and only selectively activate those. This process is called selective sparsification. Now, it must be noted that the efficiency of this process is actually dependent on how we selectively sparsify the neurons. A brute-force way to achieve this would be to calculate the activation functions for all the neurons and select the ones with the highest value of the activation function but this won’t be efficient. SLIDE proposes the use of LSH (Locality sensitive hashing), which is a more efficient way of selectively sparsifying. In fact, it is claimed that this approach when used on a 44-core CPU is more than 3.5 times (1 hour vs. 3.5 hours) faster than the same network trained using TF on Tesla V100.
What is LSH?
LSH (Locality-sensitive hashing) is a method of hashing. In this type of hashing, the inputs which are similar have a higher probability of colliding than dissimilar ones.
Let’s assume the following shapes are the inputs to an LSH function:
The LSH will try to group similar items together and here’s how the hash table will look after LSH has processed the inputs:
As can be seen from the above picture, the LSH function has grouped similar items together.
LSH usually works with two variables K and L, where L is the number of hash tables and K is the number of hash functions used per table. The inner working of the LSH algorithm and the significance of these variables is out of the scope of this article. I’ll be publishing another article where we’ll discuss these topics.
How does SLIDE use LSH?
The property of LSH to group similar items together is what helps SLIDE in figuring out the neurons that are most likely to get activated with the current input.
One LSH hash table is maintained per layer of the model. Each of these tables uses K hash functions.
For example, let’s assume a network has L layers, then there will be a total of L hash tables. Each of those tables is composed of K hash functions.
Initialization of the network
During the network initialization, the weights of the neurons are updated randomly.
Get Shubham Urkade’s stories in your inbox
Join Medium for free to get updates from this writer.
Afterward, K*L hash tables are updated. Let’s assume the hash code of weight vectors is represented as follows:
where,
l → The layer number in the neural network
a → The position of neuron in layer l.
w → The weight vector of the particular neuron represented by the above variables.
For example, if l=2, a=3, then the above equation calculates the hash codes for the weights of the third neuron of layer two.
The neuron number (a in this case) is placed in the bucket of the hash code calculated above.
It can be seen that since we are only working with a subset of neurons for a given input, the other neurons can be worked upon by the remaining inputs parallelly.
Feed-Forward pass
During the feed-forward pass, at each layer of the neuron, the hash codes are calculated:
where, l → Layer number
x → Input at layer l
These hash codes at layer l will be used to retrieve the neurons that are most likely to get activated and only calculate the activation functions for those neurons. The activations for the other neurons at this level are assumed to be 0. The same happens at the other layers too. This way only a subset of neurons are activated, which drastically reduces the compute required.
Backpropagation
At the end of the feed-forward step, the output of the network is compared with known labels. The errors are then back propagated layer-by-layer to update the weights by calculating the gradient descent.
It must be noted that after the weights have been updated, it might be required to update the hash tables too as the neurons might fall into new hash buckets now.
Summary
- SLIDE selectively activates neurons based on the input. This process is called selective sparsifying.
- Similar neurons are grouped together with LSH (Locality-sensitive hashing).
- Since we are only working with a subset of neurons for a given input, the other neurons can be worked upon by remaining inputs parallelly.
References
SLIDE research paper: https://arxiv.org/pdf/1903.03129.pdf
