The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
deep learning machine learning neural networks pruning distillation quantization size weights optimization training generalization overparameterization winning ticket winning lottery ticket arxiv
Stunning evidence for the hypothesis that neural networks work so well because their random initialization almost certainly contains a nearly optimal sub-network that is responsible for most of the final performance.

https://arxiv.org/abs/1803.03635

Abstract:
Neural network pruning techniques can reduce the parameter counts of trained networks by over 90%, decreasing storage requirements and improving computational performance of inference without compromising accuracy. However, contemporary experience is that the sparse architectures produced by pruning are difficult to train from the start, which would similarly improve training performance.
We find that a standard pruning technique naturally uncovers subnetworks whose initializations made them capable of training effectively. Based on these results, we articulate the "lottery ticket hypothesis:" dense, randomly-initialized, feed-forward networks contain subnetworks ("winning tickets") that - when trained in isolation - reach test accuracy comparable to the original network in a similar number of iterations. The winning tickets we find have won the initialization lottery: their connections have initial weights that make training particularly effective.
We present an algorithm to identify winning tickets and a series of experiments that support the lottery ticket hypothesis and the importance of these fortuitous initializations. We consistently find winning tickets that are less than 10-20% of the size of several fully-connected and convolutional feed-forward architectures for MNIST and CIFAR10. Above this size, the winning tickets that we find learn faster than the original network and reach higher test accuracy.

Authors: Jonathan Frankle, Michael Carbin

Links:
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
 Hi there. Today we're looking at the lottery ticket hypothesis finding sparse trainable neural networks by Jonathan Frankel and Michael Carbon. So this paper is sort of an empirical paper into what makes neural networks train successfully. And it comes out of the literature of pruning. So they say neural network pruning techniques, right, they have been around for a while. They can reduce the parameter counts of trained networks by over 90%, decreasing storage requirements and improving computational performance or inference without compromising accuracy. So what does this mean? If you have a neural network, let's say you just have three nodes, each layer, you have two layers here. You have a neural network here. If you have a fully connected neural network, every node is going to be connected with every node in the next layer, right? And these connections are your weights, your thetas. And you're going to train them, which means you have a number of steps in this direction. And let's say you have a test set accuracy right here. So here is steps. You're going to train them. And if you train them, your accuracy will reach a certain point, right? I'm just going to draw the end point here. Let's say you reach a 90% test accuracy. So your network generalizes pretty well. That's pretty good. So people have been wondering, these networks, they require quite a lot of storage. You know, this is nine connections right here. So three times three. And this is also nine connections. Can we make it smaller but still retain the accuracy? And this is where pruning comes in. So with pruning, people would go and after you train them. So the first step is train the full network, right? And then the second step is prune. Now when you prune, you basically select among the weights that you have that you have trained, you select the best ones in some form or another. In this case, people just select the ones with the largest magnitudes. But there are multiple techniques to do this. And this is very related to things like quantization or distillation. So with pruning, you just leave away some of the weights or most of the weights. And you hope that you still retain a pretty good accuracy right here, right? Sorry, actually, we don't need these steps thing. So you leave away weights and you retain a good accuracy. So pruning methods have been deployed successfully to make networks use less space or be faster to evaluate. Because, of course, with less numbers, you need to do less calculations. So this paper builds on top of this and it basically says, all right, if we do the following, if we now take this network that we identified after training and we just take this network and we train it from the beginning, only this sub network. Right. So three is retrain. Then it will also perform pretty well or even better under one condition. Right. So if you only train this thing, it will perform well under one condition. And the condition is that you transfer over the initial weights. So right. The question is, can we train just the small network from the beginning so that we don't have to train the big network? Right. And the paper identifies that this works if if your initial weights, theta zero of the small network are equal to the initial weights of the large network. Right. Just so just the ones where you ported them over. But basically, the short answer is no. And the reason is, if you only want to train the small network, you need to know the good initialization of these of these weights all here. And the good initialization, you only know after you've trained the large network and actually identified which of these connections make sense. You can't just take a smaller network from the beginning. You have to train the larger one. Then you know which weights and which initializations make sense. So this is the winning lottery ticket hypothesis. Basically, it states and we can read it out in full. The lottery ticket hypothesis is a randomly initialized dense neural network contains a sub network that is initialized such that when trained in isolation, it can match the test accuracy of the original network after trading for at most the same number of iterations. Right. Now, the important part here is that it contains a sub network that is initialized such that when trained in isolation. So two things are important. It is important. The structure of the network of the sub network, but it is also important. What are the initialization of the connections? So the paper kind of hints at why neural networks work at all. And the reason why neural networks work is because we've often thought of neural networks have so many parameters, how can they even generalize? The reason is the following. If we have a neural network, we throw so many parameters at it. Some of the parameters, one subset of the parameters, namely the red ones here, are going to be initialized in such a way, in such a beneficial way that training will perform, will make the network perform well. So it's initialization plus SGD on that sub network. So it is actually only a very small sub network that is responsible for the performance of the neural network. But that sub network needs to be initialized at the correct position. And by over parameterizing these neural networks so much, we actually give it combinatorically many sub networks to choose from where the initialization could be well. So because of this combinatorics, it means that if we over parameterize by some margin, then there's almost guaranteed to be a good sub network in there that can then perform well. So I hope this makes sense. It is basically not a way, it is not a magic thing where we now can train the smaller networks. It is an explanation of why the over parameterization in neural networks makes sense. Because by over parameterizing, we allow the neural networks to exploit the combinatorics to find a good, well initialized sub network that will perform well. And the evidence for this is exactly the fact that if we transfer over the sub network, it by itself will reach the same performance or actually exceed the performance. But only if we initialize it at the same point as it was initialized in the original network. So here is how these sub networks are identified. We've already hinted at that, but here is how the paper does it. So it says identifying winning tickets. First randomly initialize a neural network. This is the full neural network. Then train the network for j iterations arriving at some parameters. These are the trained parameters. Prune p% of the parameters. So of these parameters, prune some. And this is in order to know which ones you prune, you need to have first trained the full neural network. So this is the catch here. You need to train the full neural network to know which ones you must prune. And thereby you create a mask m. And then they say reset the remaining parameters to their value in theta 0. Actually you don't need to say remaining. You can just say reset the parameters to their values in theta 0. Now this is also important. This is the same theta 0 as it was at the beginning of the training. So you need to actually set them back to those exact values. And thereby you create the winning ticket. If you just want to end up with a trained network, then this remaining thing here is important. But if you then want to retrain, you can set everything back and only train the masked version of the network. And they say this will identify these winning tickets. And it will actually work better if you don't do this in what they call one shot. But if you do this iterative pruning, that means it repeatedly trains, prunes and resets the network over n rounds. Each round prunes p to the 1 over n percent of the weights that survived the previous round. Now why might that be? It might be. And this is I think a somewhat valid hypothesis that I myself put forth here. It might be that if you prune some of the weights, let's say you prune this one and this one, what you'll do is you'll put the responsibility of these weights onto other weights. So maybe on this one and this one. So as we said, they prune by looking at which weights are large. So let's say here we have the weights of the layer and these are the magnitudes of the weights. So you would prune, let's say you only want to keep two of those around. So you would prune this one and this one because these are pretty small. Here's the magnitude. And you would also prune that one. If you just do this one shot and then you would retrain and maybe these weights would end up somewhat different. But if you do this in multiple rounds, let's say you first prune one of them. So you would actually prune the smallest one, this one here. And then you retrain and then your weights actually change. And all of the responsibility that this weight carried before is now transferred onto this. So your new weights look like this. And you prune another one like this. And again, all the responsibility of this would, in my hypothetical example, fall on this one. And now if you prune a third one, you would actually prune this one because you realize this weight here, in absence of these two other weights, is actually important. So you would prune this one as well. So I think that is why this iterative pruning method might work a bit better than the one shot pruning method that they say here. So they do a lot of empirical investigation. And I just want to highlight very few of them. So that you get the gist and then the paper goes into a lot of detail and a lot of different architectures that you can check out yourself. So here we have a plot that deals with percent of weights remaining. So as you go to the right here, they drop more and more weights and realize this is a log plot. So if the dashed lines here are random pruning, which means you just drop out a certain number of weights and then you retrain. And you can see that the dashed line here, it starts dropping and just becomes worse as you have less and less weights remaining, which is exactly what's expected. You prune the network, you make it smaller, you make it less performant. And the more weights you take away, the less performing it is. But interestingly enough, if you do this pruning that they suggest and then retrain with the correct initialization, not only do you retain the same level of accuracy for very long, you see here this is 2.9 or 1.2 percent of weights remaining, but you actually go higher. So you can see here when you have 16 percent of weights remaining, there's actually a significant difference between the full network and the prune network. And that's only by simply training this winning hypothesis. So this I find very, very fascinating. And again, this is not a magic bullet that you can do from the beginning, but it does give a clue that if you could train these from the beginning, then you might actually end up at a better point. So it does actually give a practical application. Also, you see they train faster. So the blue line here is the full network over the course of training. Sorry, this should be blue. So here is training iterations and this is test accuracy. So you see the full network does something like this. Now, if you prune to 20 percent of the weights, actually train faster and you go higher. And even if you have 7 percent of the weights, you go almost as high. So this is very interesting. Only when you go to like 1.9 percent of the weights does your performance degrade again and eventually actually go lower than the original network. So that is pretty, pretty, pretty cool, I think. Now, as I said, they do a lot of investigation. And I think one of the main takeaways is that it is not only the structure of the winning hypothesis. So it's not only the structure of the sub network that makes it to be a winning hypothesis. It is actually the initialization. Here I want to show one of these plots. They have lots of plots. You can see here, for example, sorry, this is from my own annotations. Again, this is percent of weights remaining and this is test accuracy at the final iteration. And if we initialize the sub network at its original position, like this method suggests, you see, we first increase the accuracy and then decrease it after a long time. If we take the same sub network, right, but we randomly reinitialize it, then it drops much faster and actually immediately drops. So it really is about not only the structure of the sub network, but about its initialization. I think that is that is the core of the hypothesis here. A very interesting related finding that I just want to mention, I find, to be that they actually discover that the weights, so if you have a weight of the, so if you have two kinds of weights, let's actually go up to my original drawing here. If you compare how fast or how far do the weights travel in optimization space, right, so you can basically look at how far weights travel during optimization. So you take the full neural network here and you look at a parameter that ends up being in the winning hypothesis, theta, theta zero, and it goes to theta end, which let's say theta final. And you also look at parameters that don't end up in the winning hypothesis. Let's call these theta one, two, theta, also final, prime. I'm not too good at labeling. And you look at how far they travel, you'll find that the weights that end up in the winning hypothesis, they, during optimization, they travel much further in optimization space than weights that are not in the winning hypothesis, right? They just stay around much more. So it's not that the kind of good network is already contained in initialization. It's much more than the good network lends itself very favorably to be initialized by SGD, right? Because it travels farther. It means SGD has a bigger pull on it, right? I think there is a lot of things that are yet to be explored in this space, and I think this paper is a very cool contribution to our understanding of how neural networks work. All right, I invite you to check out all the experiments. They do a very thorough job. And with that, I say bye bye.
 Hi there. Today we're looking at the lottery ticket hypothesis finding sparse trainable neural networks by Jonathan Frankel and Michael Carbon.
 So this paper is sort of an empirical paper into what makes neural networks train successfully.
 And it comes out of the literature of pruning. So they say neural network pruning techniques, right, they have been around for a while.
 They can reduce the parameter counts of trained networks by over 90%, decreasing storage requirements and improving computational performance or inference without compromising accuracy.
 So what does this mean? If you have a neural network, let's say you just have three nodes, each layer, you have two layers here.
 You have a neural network here. If you have a fully connected neural network, every node is going to be connected with every node in the next layer, right?
 And these connections are your weights, your thetas. And you're going to train them, which means you have a number of steps in this direction.
 And let's say you have a test set accuracy right here. So here is steps. You're going to train them.
 And if you train them, your accuracy will reach a certain point, right? I'm just going to draw the end point here.
 Let's say you reach a 90% test accuracy. So your network generalizes pretty well. That's pretty good.
 So people have been wondering, these networks, they require quite a lot of storage. You know, this is nine connections right here.
 So three times three. And this is also nine connections. Can we make it smaller but still retain the accuracy?
 And this is where pruning comes in. So with pruning, people would go and after you train them.
 So the first step is train the full network, right? And then the second step is prune.
 Now when you prune, you basically select among the weights that you have that you have trained, you select the best ones in some form or another.
 In this case, people just select the ones with the largest magnitudes. But there are multiple techniques to do this.
 And this is very related to things like quantization or distillation. So with pruning, you just leave away some of the weights or most of the weights.
 And you hope that you still retain a pretty good accuracy right here, right? Sorry, actually, we don't need these steps thing.
 So you leave away weights and you retain a good accuracy. So pruning methods have been deployed successfully to make networks use less space or be faster to evaluate.
 Because, of course, with less numbers, you need to do less calculations.
 So this paper builds on top of this and it basically says, all right, if we do the following, if we now take this network that we identified after training and we just take this network and we train it from the beginning, only this sub network.
 Right. So three is retrain.
 Then it will also perform pretty well or even better under one condition. Right. So if you only train this thing, it will perform well under one condition.
 And the condition is that you transfer over the initial weights. So right. The question is, can we train just the small network from the beginning so that we don't have to train the big network?
 Right. And the paper identifies that this works if if your initial weights, theta zero of the small network are equal to the initial weights of the large network.
 Right. Just so just the ones where you ported them over. But basically, the short answer is no.
 And the reason is, if you only want to train the small network, you need to know the good initialization of these of these weights all here.
 And the good initialization, you only know after you've trained the large network and actually identified which of these connections make sense.
 You can't just take a smaller network from the beginning. You have to train the larger one. Then you know which weights and which initializations make sense.
 So this is the winning lottery ticket hypothesis. Basically, it states and we can read it out in full.
 The lottery ticket hypothesis is a randomly initialized dense neural network contains a sub network that is initialized such that when trained in isolation,
 it can match the test accuracy of the original network after trading for at most the same number of iterations.
 Right. Now, the important part here is that it contains a sub network that is initialized such that when trained in isolation.
 So two things are important. It is important. The structure of the network of the sub network, but it is also important.
 What are the initialization of the connections? So the paper kind of hints at why neural networks work at all.
 And the reason why neural networks work is because we've often thought of neural networks have so many parameters, how can they even generalize?
 The reason is the following. If we have a neural network, we throw so many parameters at it.
 Some of the parameters, one subset of the parameters, namely the red ones here, are going to be initialized in such a way,
 in such a beneficial way that training will perform, will make the network perform well.
 So it's initialization plus SGD on that sub network.
 So it is actually only a very small sub network that is responsible for the performance of the neural network.
 But that sub network needs to be initialized at the correct position.
 And by over parameterizing these neural networks so much, we actually give it combinatorically many sub networks to choose from where the initialization could be well.
 So because of this combinatorics, it means that if we over parameterize by some margin,
 then there's almost guaranteed to be a good sub network in there that can then perform well.
 So I hope this makes sense. It is basically not a way, it is not a magic thing where we now can train the smaller networks.
 It is an explanation of why the over parameterization in neural networks makes sense.
 Because by over parameterizing, we allow the neural networks to exploit the combinatorics to find a good, well initialized sub network that will perform well.
 And the evidence for this is exactly the fact that if we transfer over the sub network, it by itself will reach the same performance or actually exceed the performance.
 But only if we initialize it at the same point as it was initialized in the original network.
 So here is how these sub networks are identified.
 We've already hinted at that, but here is how the paper does it.
 So it says identifying winning tickets. First randomly initialize a neural network.
 This is the full neural network.
 Then train the network for j iterations arriving at some parameters.
 These are the trained parameters.
 Prune p% of the parameters.
 So of these parameters, prune some.
 And this is in order to know which ones you prune, you need to have first trained the full neural network.
 So this is the catch here. You need to train the full neural network to know which ones you must prune.
 And thereby you create a mask m.
 And then they say reset the remaining parameters to their value in theta 0.
 Actually you don't need to say remaining. You can just say reset the parameters to their values in theta 0.
 Now this is also important. This is the same theta 0 as it was at the beginning of the training.
 So you need to actually set them back to those exact values.
 And thereby you create the winning ticket.
 If you just want to end up with a trained network, then this remaining thing here is important.
 But if you then want to retrain, you can set everything back and only train the masked version of the network.
 And they say this will identify these winning tickets.
 And it will actually work better if you don't do this in what they call one shot.
 But if you do this iterative pruning, that means it repeatedly trains, prunes and resets the network over n rounds.
 Each round prunes p to the 1 over n percent of the weights that survived the previous round.
 Now why might that be? It might be.
 And this is I think a somewhat valid hypothesis that I myself put forth here.
 It might be that if you prune some of the weights, let's say you prune this one and this one,
 what you'll do is you'll put the responsibility of these weights onto other weights.
 So maybe on this one and this one. So as we said, they prune by looking at which weights are large.
 So let's say here we have the weights of the layer and these are the magnitudes of the weights.
 So you would prune, let's say you only want to keep two of those around.
 So you would prune this one and this one because these are pretty small.
 Here's the magnitude. And you would also prune that one.
 If you just do this one shot and then you would retrain and maybe these weights would end up somewhat different.
 But if you do this in multiple rounds, let's say you first prune one of them.
 So you would actually prune the smallest one, this one here.
 And then you retrain and then your weights actually change.
 And all of the responsibility that this weight carried before is now transferred onto this.
 So your new weights look like this.
 And you prune another one like this.
 And again, all the responsibility of this would, in my hypothetical example, fall on this one.
 And now if you prune a third one, you would actually prune this one because you realize this weight here,
 in absence of these two other weights, is actually important.
 So you would prune this one as well.
 So I think that is why this iterative pruning method might work a bit better than the one shot pruning method that they say here.
 So they do a lot of empirical investigation.
 And I just want to highlight very few of them.
 So that you get the gist and then the paper goes into a lot of detail and a lot of different architectures that you can check out yourself.
 So here we have a plot that deals with percent of weights remaining.
 So as you go to the right here, they drop more and more weights and realize this is a log plot.
 So if the dashed lines here are random pruning, which means you just drop out a certain number of weights and then you retrain.
 And you can see that the dashed line here, it starts dropping and just becomes worse as you have less and less weights remaining,
 which is exactly what's expected.
 You prune the network, you make it smaller, you make it less performant.
 And the more weights you take away, the less performing it is.
 But interestingly enough, if you do this pruning that they suggest and then retrain with the correct initialization,
 not only do you retain the same level of accuracy for very long, you see here this is 2.9 or 1.2 percent of weights remaining,
 but you actually go higher.
 So you can see here when you have 16 percent of weights remaining, there's actually a significant difference between the full network and the prune network.
 And that's only by simply training this winning hypothesis.
 So this I find very, very fascinating.
 And again, this is not a magic bullet that you can do from the beginning,
 but it does give a clue that if you could train these from the beginning, then you might actually end up at a better point.
 So it does actually give a practical application.
 Also, you see they train faster.
 So the blue line here is the full network over the course of training.
 Sorry, this should be blue.
 So here is training iterations and this is test accuracy.
 So you see the full network does something like this.
 Now, if you prune to 20 percent of the weights, actually train faster and you go higher.
 And even if you have 7 percent of the weights, you go almost as high.
 So this is very interesting.
 Only when you go to like 1.9 percent of the weights does your performance degrade again and eventually actually go lower than the original network.
 So that is pretty, pretty, pretty cool, I think.
 Now, as I said, they do a lot of investigation.
 And I think one of the main takeaways is that it is not only the structure of the winning hypothesis.
 So it's not only the structure of the sub network that makes it to be a winning hypothesis.
 It is actually the initialization.
 Here I want to show one of these plots.
 They have lots of plots.
 You can see here, for example, sorry, this is from my own annotations.
 Again, this is percent of weights remaining and this is test accuracy at the final iteration.
 And if we initialize the sub network at its original position, like this method suggests, you see,
 we first increase the accuracy and then decrease it after a long time.
 If we take the same sub network, right, but we randomly reinitialize it, then it drops much faster and actually immediately drops.
 So it really is about not only the structure of the sub network, but about its initialization.
 I think that is that is the core of the hypothesis here.
 A very interesting related finding that I just want to mention, I find, to be that they actually discover that the weights,
 so if you have a weight of the, so if you have two kinds of weights, let's actually go up to my original drawing here.
 If you compare how fast or how far do the weights travel in optimization space, right,
 so you can basically look at how far weights travel during optimization.
 So you take the full neural network here and you look at a parameter that ends up being in the winning hypothesis, theta,
 theta zero, and it goes to theta end, which let's say theta final.
 And you also look at parameters that don't end up in the winning hypothesis.
 Let's call these theta one, two, theta, also final, prime.
 I'm not too good at labeling.
 And you look at how far they travel, you'll find that the weights that end up in the winning hypothesis,
 they, during optimization, they travel much further in optimization space than weights that are not in the winning hypothesis, right?
 They just stay around much more.
 So it's not that the kind of good network is already contained in initialization.
 It's much more than the good network lends itself very favorably to be initialized by SGD, right?
 Because it travels farther.
 It means SGD has a bigger pull on it, right?
 I think there is a lot of things that are yet to be explored in this space,
 and I think this paper is a very cool contribution to our understanding of how neural networks work.
 All right, I invite you to check out all the experiments.
 They do a very thorough job.
 And with that, I say bye bye.