The Lottery Ticket Hypothesis - Paper Discussion

Hi everyone and welcome to this first video. Before we start digging into this paper, let me introduce myself. So I'm Valentin De Matos, lead IA engineer at Gladia, and I was thinking about creating videos which will be composed, I guess, in two different parts. The first one will be discussing or explaining a paper in this case it's the Lottery Tickets Hypothesis Fitting Sparse Trainable Neural Networks paper by Jonathan and Michael. And in a second video, I guess it will be a spirited video, we will try to reproduce the results of this paper, and of course it will result in a GitHub project that you can use or explore to reproduce yourself the paper and play with it. So let's start to explore this paper, let's go! Today, like I was saying, we will be exploring the lottery ticket hypothesis via sparse trainable neural network. I found it really both interesting and funny in the hypothesis states. Because like you can guess in the title, the main goal of this paper is to bring, um, a hypothesis, an hypothesis, which is, I found really interesting and funny. So let's start by reading what does this hypothesis state. The Lottery Ticket Hypothesis states that a randomly initialized dense neural network contain a subnetwork that is initialized such that when trained in isolation, it can match the test accuracy of the original network after training for at most the same number of iterations. Let me rephrase this statement. It says that imagine you have a neural network, in, in this case it's It's a really simple neural network. So this neural network, let's call it NetworkO. Oh, see you later. You train it. So in our case, we want to train it for the MNIST datasets. We train it for G iterations. So let's not G. And after G iterations, well, your network will be trained and will be able to tell, oh hey, this is the 6th number, so I will tell you this is 6. And the paper states that in this network that you did train, it exists— let me zoom in again— it exists a second, or more like a subnetwork, which is smaller. So let's delete or remove random weights and connections, neurons, and that can match the same accuracy of your original neural network with at most the same number of training iterations. So this means that this neural network, this new neural network, this sparse neural network, will be, I guess, more efficient with the same test accuracy. So the big question is, of course, how do we find this subnetwork? First of all, they call this subnetwork, see, let's find it back, winning tickets. So the goal is how can we find this subnetwork which is called winning tickets? And for that, the paper describes us 4 main steps. First, you randomly initialize a neural network, so basically you just create your neural network like you will normally do in TensorFlow or in PyTorch or anything. You train it for G iterations like we said, you just take data, you put it to your network, you train it again and again for G iterations steps. And when you reach this G's iteration, you arrive at a certain set of parameters, so your network is basically trained. You will prune a certain percentage of those parameters of your network. So this is a parameter of your network which will result in a certain mask, and the force And last step will be to reset the remaining parameters to the original values before training, creating the winning tickets. Again, let me rephrase it. Basically, it states that— okay, let's remove all that. You have your untrained neural network, so currently we are at step 0, and you give it numbers or images of MNIST It gives you predictions. At first it will be bad, and when you reach iteration G, so the last training iteration, you will have a trained neural network. And what you will do is you will prune your neural network, removing some weights, some connections, and maybe some full neurons. So let's say it's those neurons, you will remove it, set the remaining connections and weights to their original values at step 0, so before training, and this will result in your winning tickets. But not that, they say they do not randomly reinitialize the remaining weights and connections. They set it back to the original value before training, which is a really important point. So for that, you have two different ways of doing the third step. You could do it in a one-shot way, so you just, you know, train your model, train it, prune it, reset remaining weights. Or you can do it in an iterative pruning way, so with n different rounds of pruning, each round pruning, uh, only a part of the weights that survived the previous round of pruning. And it states that in their result The result shows that iterative pruning finds winning tickets that match the accuracy of the original neural networks at smaller size than does one-shot pruning. It means that, in a way, iterative pruning results in more efficient, or more, or let's say smaller neural network compared to winning tickets found with one-shot pruning. Okay, now we know a bit more about what's the statement, what's a winning ticket, what's the hypothesis. Let's dig in a bit about the different experiments and results. In the paper, they use, um, 6 different neural networks. First, LeNet-300-100 trained on MNIST. Then Conv2, Conv4, Conv6, which are a smaller-sized VGG19 architecture. And of course you have VGG19 and ResNet18. And all of these 5 networks are trained, adapt and train to the CIFAR-10 datasets, which is said right here. So let's explore the different results. First, let's start by exploring the results for the LeNet architecture trained on MNIST, which is basically only a fully connected neural network. In this, um, figures, we can see the model accuracy on the test sets regarding the training iteration, the fraction of remaining weights, weights in the network after pruning. And the really interesting thing, or the most important thing, is that you can see in the blue line you have the full neural network which is not pruned. It's only the original neural network. After training, well, after G duration training step. And in orange and in green, you have a sparse version of this neural network, which is so pruned. And you can see that both the orange and the blue plots shows better results than the original neural network, which means that the lottery ticket hypothesis, do show really interesting results. So you can really identify and find winning tickets. Those winning tickets are smaller. This neural network is around half the size in a way than the original network, and it trains both faster, where you can see right here. The accuracy increases faster and it reaches higher test accuracy compared to the original neural network. And so the question is, of course, how far can you prune your neural network before decreasing the final accuracy? So they tried to find And they go a bit further with, here in blue you still have your 21, your 21, you know. In red you have a neural network with only 7% of the weights remaining, in purple 3.6%, and in brown around 2%. You can see that starting from 7%, the accuracy starts to drop compared to 21%, still dropping, uh, when you go to 3.6%, and starting from around 2%, you drop under the original model accuracy. But I find it really amazing to know that you can prune your neural network in a way that only around 4% of the remaining connections still exist, but you reach higher accuracy compared to the original neural network. And even it's, it's training faster, which is mind-blowing for me. Okay, so let's zoom out of it. Remember previously we said that in our fourth step to find the winning ticket, so this sparse neural network, we do reinitialize the remaining parameters to their original values before training, not re-randomly initialize it. We, we take the original values before training and we use it again. And so to verify, it's important to use again those initial values. They compare, they do exactly the same experiments with the same data, the same architecture, but with re-randomly re-initialized weights. And you can see that, compare right here, when you prune your neural network, you reinitialize your remaining weights in a random way, you do lose accuracy. It's really important to initialize the remaining weights to their original values before training. And which again, I find really interesting. So because it really shows that in a way, in your neural network, in your dense neural network, you do have, you do have an over-parameterized model basically where you can, you have, it's not like you can, it's you have a subnetwork in your network that is smaller, that can reach the same accuracy of your original network, and that can even be trained faster. And you have a way to find it. Which, well, it's really expensive in a computational way to find because, well, you have to train at least one time your model, then prune it, and initialize again, then retraining, and again and again and again and again. Well, you understand me. Okay, so like I showed you, those networks do reach higher accuracy But you have just a quick diagram on the next page here, right here, where you find in a more cleaner way that those networks also train faster. Because here on the x-axis you can see the percent of weights remaining after pruning. So you have your sparse neural network starting from here, and here you have, see, a list of iterations on the validation set. So basically how many iterations you will need to reach your trained neural network. In blue, you have the iterative pruning, so way to find the winning tickets. In green, you have the one-shot way to find those winning tickets. And in In both red and orange, you have the same way of pruning but without trying to find the winning ticket. So basically, you just prune your neural network and reinitialize the remaining weights in a random way and not to their original values before training. And you can see that the blue diagram plots is always training faster compared to the randomly reinitialized neural network, which shows that those winning tickets do effectively train faster compared to randomly reinitialized neural network or even their original network without even pruning. Because you can see that you need around 5,000 iterations when you don't prune your neural network, and at around 13% of the weights remaining, you are— who could not say the exact number because you don't have the number writing, but you can see that it's really under the 5K iteration. So, source neural networks are indeed trained faster. And now let's just see the same experiments with convolutional neural networks. We'll do it a bit faster because we already see this statement, so this statement, and you can see again in blue the Conv2 architecture with iterative pruning And in DHBLOO, the same architecture, but every time you prune, you reinitialize the weights. And you can see again that you do indeed really need far less training iterations with the winning tickets resulting neural network compared both to their original neural network and to a neural network that will be pruned and then re-randomly reinitialize, which confirms the previous statements. Okay, so we can now have more conjecture, I will say, which is page 3 right here. So the conjecture, the lottery ticket conjecture, states that SGD seeks out and trains a subset of well-initialized weights. Dense randomly initialized networks are easier to train than sparse networks that result from pruning because there are more possible networks from which training might recover a winning ticket. So the question was, okay, so you do, okay, indeed have some sparse neural network which is smaller neural network, again, which fit at least the same accuracy in around the same amount of time or a bit less. But why can't you just train your sparse neural network starting from the start, as the start, against starting from a deeper neural network? The conjecture is that in that many connections SGD have more ways to find winning tickets compared if you would have, you know, an already sparse neural network where you have far more less possible winning tickets compared to U-Net version model. Explaining why you must start from this dense neural network, um, over-parameterized architecture, before having your sparse resulting neural network. And this is why it states right here. And so to conclude, um, they say few contributions which are, first, again, you do have a sparse neural network in your original neural network which can reach the test accuracy, or at least the same test accuracy, or even more, that can be trained faster, that generalize better, which I have not shown you in this video to not have a really long video. But I invite you to read the paper. And they say, well, it's really interesting and we should continue to explore this way and try to understand why, and in a way start to explain why neural networks works. And indeed, you have some papers after that which explore this hypothesis a bit deeper, and we will not cover it in this video, but I think I will try to do a second video exploring those different papers. So yeah, it's basically, basically it's for this video and for this paper. It was the Lottery Ticket Hypothesis: Finding Sparse Trainable Neural Networks by Jonathan and Michael. Bose from MIT. And this was my first video, so feel free to share me any thoughts you have on it, both good and bad, I guess. Well, if you have anything in your head that could improve those type of videos, um, feel free to share me. That's it for me, um, see you in the next video, I guess.