SynFlow: Pruning neural networks without any data by iteratively conserving synaptic flow
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper initialization lottery ticket hypothesis pruning training magnitude snip grasp init xavier glorot he flow layer collapse iterative recompute stepwise memory fast prune weights feedforward layer neural network
The Lottery Ticket Hypothesis has shown that it's theoretically possible to prune a neural network at the beginning of training and still achieve good performance, if we only knew which weights to prune away. This paper does not only explain where other attempts at pruning fail, but provides an algorithm that provably reaches maximum compression capacity, all without looking at any data!

OUTLINE:
0:00 - Intro & Overview
1:00 - Pruning Neural Networks
3:40 - Lottery Ticket Hypothesis
6:00 - Paper Story Overview
9:45 - Layer Collapse
18:15 - Synaptic Saliency Conservation
23:25 - Connecting Layer Collapse & Saliency Conservation
28:30 - Iterative Pruning avoids Layer Collapse
33:20 - The SynFlow Algorithm
40:45 - Experiments
43:35 - Conclusion & Comments

Paper: https://arxiv.org/abs/2006.05467
Code: https://github.com/ganguli-lab/Synaptic-Flow
My Video on the Lottery Ticket Hypothesis: https://youtu.be/ZVVnvZdUMUk
Street Talk about LTH: https://youtu.be/SfjJoevBbjU

Abstract:
Pruning the parameters of deep neural networks has generated intense interest due to potential savings in time, memory and energy both during training and at test time. Recent works have identified, through an expensive sequence of training and pruning cycles, the existence of winning lottery tickets or sparse trainable subnetworks at initialization. This raises a foundational question: can we identify highly sparse trainable subnetworks at initialization, without ever training, or indeed without ever looking at the data? We provide an affirmative answer to this question through theory driven algorithm design. We first mathematically formulate and experimentally verify a conservation law that explains why existing gradient-based pruning algorithms at initialization suffer from layer-collapse, the premature pruning of an entire layer rendering a network untrainable. This theory also elucidates how layer-collapse can be entirely avoided, motivating a novel pruning algorithm Iterative Synaptic Flow Pruning (SynFlow). This algorithm can be interpreted as preserving the total flow of synaptic strengths through the network at initialization subject to a sparsity constraint. Notably, this algorithm makes no reference to the training data and consistently outperforms existing state-of-the-art pruning algorithms at initialization over a range of models (VGG and ResNet), datasets (CIFAR-10/100 and Tiny ImageNet), and sparsity constraints (up to 99.9 percent). Thus our data-agnostic pruning algorithm challenges the existing paradigm that data must be used to quantify which synapses are important.

Authors: Hidenori Tanaka, Daniel Kunin, Daniel L. K. Yamins, Surya Ganguli

Links:
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://discord.gg/4H8xxDF
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
 Hi there! Today we're looking at pruning neural networks without any data by iteratively conserving synaptic flow by Hidenori Tanaka, Daniel Kunin, Daniel L.K. Yamins and Surya Ganguly. So this paper on a high level does what the lottery ticket hypothesis does, but does so without any data. It prunes a neural network at the beginning and it does so. It's able to do that because it claims that its algorithm avoids this problem called layer collapse and then is based on conserving a quantity they call the synaptic flow. And we're going to look at this and it's a pretty cool algorithm. It seems to work pretty well. As always, if you want to help out, you can share this video and let me know in the comments what you think of it. I do read the comments and I would love to hear from you. Alright, let's dive in. So they're saying, pruning the parameters of deep neural networks has generated intense interest due to potential savings in time, memory and energy, both during training and at test time. Recent works have identified through an expensive sequence of training and pruning cycles, the existence of winning lottery tickets or sparse trainable sub networks at initialization. So what is this paper talking about? If you don't know much about pruning, here is kind of a basic overview. So if you have a neural network that consists of many, many layers of neurons, what you can do, that one way of pruning that, what the goal is, is to end up with a small neural network that performs well. But for now, we have a big neural network that doesn't perform well. It hasn't been trained yet, right? So what you can do is you can first train the neural network. And then you have a big neural network that performs well, and then you can prune it. Now, a lot of times, a lot of the time this has been seen as sort of the pruning way. You would train the big neural network and then you would prune it, because the other way was not feasible. First pruning and then training was not feasible. You might ask, okay, we might just want to start with a small one. And yeah, that's correct. So what does this first way buy you? This first way buys you mainly two things. So imagine this network right here is much smaller than the original network. So it is less, it uses less storage. So you can potentially, if you want to ship it to like a customer over the internet, you maybe instead of a gigabyte, you only have to transfer a few megabytes. And that's pretty cool. The second thing, if you prune in the correct way, you can also make it faster because now there's less weights to multiply with, you can actually make it go faster. So pruning is a now this this and it combines with techniques called distillation and so on is our ways to make the networks smaller and faster. So if your customers are for example, on on mobile phones, then you can ship you can train a big network to a good performance on your big GPU server, and then ship it out to a mobile phone. Once it's small, and it will perform fairly well on that mobile phone without GPU. So what about this other way? Now, in order to do the other way, we would sort of have to have an idea which one of these big networks which sub parts of these layers are the good ones, right in order for us to do this first prune and then train. The interesting thing is that the paper the lottery ticket hypothesis, I've done a video on this and we've also interviewed the author on our ML Street talk podcast. This paper has shown that this is in fact possible. A long time people have thought we need the big network in order to train, right? We sort of the bigness of the network, the full connectedness of the network is required for the training dynamics. But this paper has shown this is not possible, you can prune at the very beginning. Now, what does it do? It first trains a neural network, like in the olden days, then it prunes the neural network. And then it remembers which connections of the train neural network it has pruned. And then it simply goes back to the beginning of training right here, up here, and says, I now know which connections are important. And I'm simply going to prune all the other connections other than these ones. And then interestingly, if you prune first, and then train, that works just as well and can actually work even better. The interesting thing here is that I mean, this is a big, big cycle. But the interesting thing that the paper demonstrates is that this is even possible, right? People thought it wasn't possible. And this paper demonstrates if you only knew if you only knew which ones you must retain, you can prune at the beginning of training. The lottery ticket hypothesis paper, though still requires to actually train the full network and then do the pruning, like in a classic way in order to find out which ones you need to prune and which ones you don't. This paper right here takes that idea and says, can we find can we find a pruning algorithm that prunes at the beginning of training, yet does not have to train the full network, in fact, doesn't look at any of the data? Okay, and this is are going to be our starting point. So their story is going to be, it's quite an involved story. And I think the overview is important. Well, as we go through the paper. So first, they named this problem called layer collapse. Now, layer collapse is going to be whenever a pruning algorithm removes the entirety of a neural network layer, which means that no information can flow anymore. And therefore the network can't train. And they claim that this is the main problem, why these current pruning algorithms cannot achieve very high pruning ratios, so can like very high compression ratios is because they do premature layer collapse, they then formulate this maximal critical critical compression axiom that has sort of a guiding principle to build pruning algorithms. Second, they show that this quantity called synaptic saliency, a general class of gradient based scores for pruning is conserved at every hidden unit layer of a neural network. So they show that these are conserved. And they show this because this is their, their argument is going to be first, the argument is layer collapse is a problem. The second argument is these things are conserved and these, the conservation of the synaptic saliency leads to the layer collapse. And we're going to see how that happens. And then third, they say the solution to that is iterative pruning. So they show this at the at the example of iterative magnitude pruning, which we know avoids layer collapse. So iterative magnitude pruning is something that happens in this lottery ticket way of of doing it. This lottery ticket way, you can actually do it not in one step, but it tends to work better when you want to go from 100% of your weights to just 5% of your weights, it tends to work better if you do it in stages. So first you go to 90% to 80 to 70 and so on down to your desired thing. And this iterative procedure, they claim is what is what circumvents this problem of layer collapse. And then at last, they say we proved that a pruning algorithm avoids layer collapse entirely and satisfies blah blah blah, if it uses iterative positive synaptic saliency scores. So they bring it all together and say, if an algorithm satisfies our axiom, and if the algorithm is an algorithm that uses these saliency scores, like this one here, and if the algorithm is iterative, then it is not going to be subject to layer collapse. And therefore, it is going to be able to compress to a very high compression ratio. And then they actually do suggest an algorithm, this iterative synaptic flow pruning, SYNFLOW, that does all of this and never looks at any data. All right, this is quite a story. But remember what we're doing. First, layer collapse is a problem. Second, why is layer collapse a problem? It's because of this synaptic saliency conservation. Third, we can avoid it by doing iterative pruning. And lastly, this algorithm does it without looking at data. Okay, so layer, layer collapse, layer collapse is a pretty simple phenomenon. I've already said it, if you have a neural network, and it has a bunch of layers, and let's draw a couple of neurons here, and the neurons are connected to each other via connections, connections, connections, connections. And you have a pruning algorithm. Now the pruning algorithms they consider here are so called single shot pruning algorithms. What they do is they look at the neural network, and this can be before training or after training. But at some point, they look at the neural network, and they assign a score to each of these weights. Like they'll say, you're a one, you're a five, you're a nine, and so on. And then they simply prune away the lowest scores. Okay, and you tell the network what compression ratio you want to you tell the network, for example, please prune away 90% of the connections. So these algorithms would look would assign the scores once and then remove the bottom 90% of weights. Okay, like this. So those are the single shot pruning algorithms. Now what is layer collapse? Layer collapse is whenever an algorithm removes all of one layer, because maybe so here was a nine, maybe you have like 111213 here. Okay, so and then you're in you're in this situation right here. And the algorithm is pretty, is pretty dumb. It's simply removing the bottom 90% of the connections. And here it figures I need to remove one more to meet that goal. I remove the one with the lowest score, I'm going to remove this one. And it's pretty obvious that now no more information can flow from the beginning to the end of the network because, well, what's where is it going to flow to? It's a bit more complex than that. Like, you can't just retain a layer like a connection. For example, if this were a connection, there would also be no information flow because you'd have no outgoing connection here. But ultimately, layer collapse is whenever an entire layer is removed. Okay. And they they do say somewhere that that's the case. I think layer collapse here, layer collapse occurs when an algorithm prunes all parameters in a single weight layer, even when prunable parameters remain elsewhere in the network. So I'm not as such, I'm not sure that this is like a giant problem. It gets to be a problem. But it could be circumvented fairly easily, right by simply saying, if you're about to prune a connection that's integral to the information flow from the start to the end, don't prune that connection, prune some other connection, right, and then you could simply avoid that. And I'd be interested in how that works out. So but in this case, for purposes of this paper, they simply consider algorithms that assign a score and then prune the bottom couple of percent, okay, for so we don't want any like handcrafted rules in here or something. So they look at this quantity called the max compression. The max compression is a quantity that's basically the maximum achievable compression while still avoiding layer collapse. And they say, for example, for a network with L layers and n parameters, the max compression is n over L, which is basically means every layer only has one parameter remaining and therefore, and if it's the correct one, therefore information can flow from start to the end. All right, so this is the maximum achievable compression, anything beyond that would automatically induce layer collapse. Now, anything before that could induce layer collapse, but there is a way to compress the network to the same level without inducing layer collapse. And their point is basically that these other compression algorithms that they compare with, they always they always induce layer collapse before they actually have to because they cut off a connection that leads to layer collapse before they like there would be another connection that they could cut off that would not lead to layer collapse. And of course, if you are layer, if you have done a layer collapse, then you accuracy immediately drops to zero or to random, because no more information flow. So they look at these things here, random pruning is where you simply assign a random score to each connection. Magnitude pruning is what the lottery ticket hypothesis does, but just they look here at a single shot. So you simply look at the magnitude of the weights and this can be before or after training. I think they do it after training here, which is classically done. You look at the magnitude of the weights and you prune the bottom 90% away. They there are also two more advanced methods, these SNIP and the grasp piece of SNIP and grasp, which look at the gradient of the training loss in the network and they decide according to that gradient, which which things to cut and which things not to cut away. The grasp even involves the Hessian right here. So they're fairly, you know, complex method that have some thoughts behind them about why they do what they do, yet they all induce layer collapse before they actually have to. So they define this thing here called the critical compression. The critical compression is the maximal compression ratio a given algorithm can achieve without inducing layer collapse. So the critical compression here is basically whenever that algorithm goes to zero, that's the critical compression. That's kind of the farthest you can push the algorithm without him without sorry, German speaker, without it induced without it inducing layer collapse. Okay, so you can see that for these baseline algorithms, the layer collapse occurs way below the theoretically possible max compression. And we're going to see that in their algorithm, this sin flow, that this max compression is achieved. And it's actually achieved without any of these handcrafted rules that I mentioned, it is the algorithm by design already achieved this maximum compression ratio. So they formulate this here as a guiding principle, they formulate as an axiom, I would, I would rather say it's like this kind of a, it's kind of a guiding principle of building these algorithms that any algorithm you build should have. So the critical compression ratio of a pruning algorithm applied to a network should always equal the max compression of that network. It basically means when you build a pruning algorithm, if you push that pruning algorithm to its limits, it should not do layer collapse unless it absolutely needs to. Okay. Again, the extent of this problem, I don't, I don't know, but they do demonstrate that that they can push their algorithm a fair bit further. Now, without inducing layer collapse, you already see that these other algorithms, like in this regime, apparently layer collapse hasn't happened yet because they still have sizeable accuracy, but there's still, you know, there is a reasonable difference here between those and the sin flow algorithm. So I'm not too convinced yet that layer collapse as such is the problem because they have a difference before their layer collapsing, as you can see right here. And I have the feeling that this difference here is due to this iterative procedure and not actually due to the phenomenon of layer collapse. But yeah, so if it were only layer collapse, what you'll see is that they do the same, the same, the same, and then at some point it's like, boom, now I have layer collapse. Okay. Yeah. So the layer collapse story, I'm not sure, but it's part of the story. So let's, let's go with that. The second part, which is kind of disconnected. So they established two things. They established a layer collapse problem, and now they establish the synaptic saliency, which then later they're going to connect to the layer collapse. So the synaptic saliency, they say is a score, is any score metric that can be expressed as the Hadamard product of this thing with the parameters. Okay. So each parameter is going to be multiplied by the gradient of some function with respect to that parameter. They say where R is a scalar loss function of the output of a feed forward neural network parameterized by theta. Okay. So many of these pruning algorithms can be formulated in this framework right here. And their, their algorithm can also be formulated in this framework. So you can see the score that the algorithm assigns to a weight can be defined as such. And as I said, many fall into this category or are similar to this, especially for example, they say when R is the training loss L. So this is the simplest case you take, you put data through the network, and then you take the training loss of that data and you sort of back propagate it. And now you're going to prune these connections according to how big the gradient is. If you say the gradient is very big, that must mean the connection is very important because there's lots of information flowing through it. So if it's a training loss L, the resulting synaptic saliency metric is equivalent to the score metric used in skeletonization, one of the first network pruning algorithms. The resulting metrics metric is also closely related to this right here. Now this you can see it's not exactly the same, but it's closely related to the one used in this snip baseline and also closely related to this thing right here used in grasp, where it's not just the gradient, it's actually the gradient multiplied by the Hessian to account for curvature. Okay, so they're going to investigate this synaptic saliency in neural networks. They formulate two theorems right here about the conservation of synaptic saliency. Remember synaptic saliency is any score that respects this that is built like this, any score S. The conservation of synaptic saliency, all synaptic saliency metrics respect two surprising conservation laws that hold at any initialization and step in training. So these are not usually like in distribution or something like this with high probability. These things hold at any point in the neural network. First is the neuron wise conservation of synaptic saliency. For a feet forward neural network with homogeneous activation functions and a homogeneous activation function is an activation function that can be expressed like this, for example, relu's fall into that category, the sum of the synaptic saliency for the incoming parameters is to a hidden neuron is equal to the sum of the synaptic saliency for the outgoing parameters from the hidden neuron. So what does it mean is actually pretty simple. If you have a hidden neuron and you look at all the incoming weights and you look at their synaptic saliency, which is this S score of each of these weights, like what would the pruning algorithm assign to that? And you look at the outgoing ones, then the sum of all the incoming ones is going to be equal to the sum of all the outgoing ones. So that's pretty interesting. And they extend that to layer to the entire network. So an extension of that network wise conservation of synaptic saliency, the sum of the synaptic saliency across any set of parameters that exactly separates the input neurons from the output neurons of a feet forward neural network with homogeneous activation functions equals that. So it basically says it remains equal. So what does it mean? What does it mean to exactly separate the input from the output? That's basically the definition of a layer in a neural network. So what they're saying is that you have a bunch of layers. And if you look at a particular layer like this one here, and you look at the incoming connections, and you sum up all of their synaptic saliency, that's going to be equal to the sum of all the synaptic saliency of the outgoing connections of that layer. And it can also apply to like a group of layers and so on. But the synaptic saliency is conserved in that way. Now, why is that important? And here is where we make the connection with the layer. Was it later drop layer? Whatever. Okay, the fact that the fact that these algorithms tend to drop entire layers before they have to, if you have in your network layers that are of different sizes, so you have large layers, and then smaller layers and smaller layers, what will happen is that since the synaptic saliency is conserved, the sum is conserved, if you have more connections in one layer, so lots of connections, lots of connections, and in the small layers, you don't have as many connections, the sum is equal. So that means each individual one here is much, much smaller. So the S is very small for each individual one here, and the S is very large in there. That means the pruning algorithm is going to really, really kill off these connections in the big layers. And it's actually going to kill them off to a point where it probably is going to eliminate that layer before it even prunes many of the connections of the small layer, just because of that conservation fact. And they do experiments like this. I think there's an experiment up here where I like this one down here better, where they basically show that you have inverse layer size on the bottom, and you have the average score that the pruning algorithm assigns to any connection. Now, these, as we've seen, they're not exactly assigning the scores of this saliency, but they're very close to it. The Synflow algorithm does exactly assign the synaptic saliency as the score for the pruning. Now, we've basically seen that this leads to a bad result, but the synaptic flow is going to compensate for that. But in essence, as you can see, as the layers get, so inverse layer size grows, which means that layer size shrinks as the layer size gets smaller, the average score of the connections in the layer is higher and higher, which basically means that the pruning algorithm, if you just let it go by itself, it's going to kill off the smaller, sorry, the larger layers first because they have the smaller scores. And you can see that even though the other algorithms don't conform exactly to that, they conform to this approximately. So these here, because their score is closely related to what the Synflow does, and the magnitude pruning, because mostly, because now I'm not sure if that's at the end of the training, at the beginning of the training, if you just initialize, then the score is going to be proportional to their magnitude and their magnitude is determined by the initialization scheme. And the initialization scheme is most of the time, like modern initialization schemes, compensate for the fact that you have different number of incoming and outgoing connections and therefore they would automatically assign a higher initialization constant to layers that have the lower number of parameters. So even the magnitude pruning will conform to this. Now, it might be absolutely reasonable to say that that's also the case at the end of training because most parameters aren't going to move super much during training. So this still approximately holds, as you can see here. Of course, the random one doesn't do that. Yet, because you prune randomly, you're still absolutely subject to this layer collapse. In fact, in the random one, the smallest layers would be the ones to go away first because it's just more probable. Okay. So we've discovered that if you do something like saliency scoring or something that's correlated to it, then you're going to remove the biggest layers first. And that's a problem. And that's what they say. This fact of this conservation laws and the single shot nature of these algorithms that they only assign scores once and then they prune away whatever the bottom such and such percent are leads to layer collapse. I think we've established this now that the combination of the two things leads to layer collapse. Now they make a little bit of an excursion and they say there is actually something that doesn't run into layer collapse. And that's iterative pruning algorithms. So specifically, they look at magnitude pruning. They say magnitude pruning, which remember is also if you do it single shot, it also runs into layer collapse. Magnitude pruning avoids layer collapse with conservation and iteration. So because it iterates, it avoids that. And that's what these lottery ticket hypothesis paper does. It does it iteratively removes a couple of connections, then it retrains the network, basically recomputes the magnitudes and therefore recomputes the scores. And then it prunes again, and then it recomputes and and prunes again. And by recomputing, you can basically these some of the connections that weren't important before, but just survive the pruning, they can now be like, wait, I have now way more responsibility as a connection, and they will shoot up in importance to avoid being pruned. So you can see if you push your network to a sorry to a high compression ratio, then if you just do this single shot pruning, you run into this layer collapse at some compression ratio, you simply crash to random performance or zero performance. Yet, if you do multiple iterations, you can see here already two iterations, then it's much longer before you run right here into layer collapse. And if you do three iterations, you do much more. Now this the three iterations doesn't mean you prune more like at this, at this point right here to tend to the one. All of these things prune nine out of every 10 connections. It's just the thing that has three iterations prunes maybe first three and then again, three and then again, three out of the 10. Whereas the one iteration would prune all of the nine at in one go. Okay. And they give a reason for this they give they say that it's the fact that gradient descent encourages conservation. So they give a little toy example here they say to better understand the dynamics of the IMP algorithm during training, the smaller we will consider the a differentiable score, this one. So this is not exactly magnitude pruning, but it is very close, right? The squared it's just the square of the parameter instead of the absolute value of the parameter. They say it's algorithmically equivalent to magnitude score. Consider these scores throughout training with gradient descent on a loss function using an infinitesimal step. In this setting, the temporal derivative of the parameters is equivalent to that. And thus the temporal derivative of the score is this. So now they're going to look at how does the score evolve when they train the network and the score evolves exactly as the negative to the saliency. Surprisingly, this is a form of synaptic saliency. And thus the neuron wise and layer wise conservation laws from section four apply. In particular, this implies that for any two layers of a simple fully connected network, then this quantity holds. So this is not new. But what it basically says is that through training, these connections equalize the saliency again. So if you have a very big layer, and here a very small layer, and because it's a big layer, these scores are very much lower, right? It's just little s and here it's big s per layer. But then if you prune away, and you run gradient descent on this, these scores will tend to become bigger. And in this case, these weights will tend to grow in magnitude. Because you've pruned away the others, they now have more signal probably flowing to them and more gradient flowing to them. And therefore they're going to grow in size. And therefore, their score is going to be bigger. So this gradient descent of this iterative procedure makes the scores better for that. So basically counteracts the layer collapse. So they put all of this together and say, theorem three, iterative positive conservative scoring achieves maximal critical compression. If a pruning algorithm with global masking, and global masking means that you rank all of the connections and then prune from all of the connections, it's a difference to layer wise masking where you say I want to remove 90% of each layer, which sounds like it would avoid layer collapse, but also it works a lot worse than the global one, the global strategy. Assigns positive scores that respect layer wise conservation. And if the algorithm, so respecting layer wise conservation, it basically means your score should be, or if your score is a saliency score, then that's the case. And if the algorithm reevaluates the scores every time a parameter is pruned, then the algorithm satisfies the maximal critical compression axiom. Okay. So that's basically saying that if you have any algorithm that prunes with a saliency score, like theirs is going to do, is going to be able to be pushed to the limit until the maximal capacity is reached if you reevaluate the scores every time a parameter is pruned. So this is basically saying that whatever the lottery ticket hypothesis paper did with magnitude pruning, if you do it with saliency based pruning, you're guaranteed to achieve the maximum possible compression if you push it. But of course we know that whatever the lottery ticket hypothesis paper did is impractical because it needs to retrain the network every single time it wants to prune. Right? So if you want to do this after every parameter, that's going to be a long time. It's going to be impractical. We ideally want to prune the network before we even look at any data. And they're going to do exactly that with the SYNFLOW algorithm. They say theorem three directly motivates the design of our novel pruning algorithm. SYNFLOW that provably reaches maximal critical compression. First, the necessity for iterative score evaluation discourages algorithms that involve back propagation on batches of data and instead motivates the development of an efficient data independent scoring procedure. Second, positivity and conservation probably motivates the construction of a loss function that yields positive synaptic saliency scores. We combine these insights and introduce a new loss function where the one is the all one vectors. Okay, so this is the loss function of their saliency scores. And this might seem like... So what do we have? We have the parameters of layer L, the absolute product, sorry, the absolute value of those parameters, and then you simply multiply all of the layers together. And you have this product here with the ones on the side. So this is a quadratic form, sort of. Okay, this might seem a bit weird, but in practice, and this is also what happens in their code, you can do something pretty easy. So first, you have to transform all your weights to their absolute values. Now in their code, you can look at it, they do remember the signs for later. So but first, you convert all of them to their absolute values. Then second, you simply take a data point that is filled with ones that literally the number one. So if your if your input is an image, you just put a one at each pixel, you feed it through the network with all of these positive weights, and you get out some output, you get some output vector, okay, then you simply you need to do this inner product with the one vector, which is simply a sum, right? I don't I don't get why they it's a bit of a funky way of writing a sum, right? You simply sum that up to get a to get a single number. And this single number now is your is your pseudo loss function. It's simply the loss function that an all one data point gets when the when the loss function is just the sum of the outputs. That's that's it. That's it. And then you back propagate that loss to you back propagate that loss to the layers. Right? So this is our remember this is not the score itself, but our score is going to be the derivative of our with respect to a weight times that weight. Okay, so you want to back propagate, and then you multiply each of these weights by the back propagated signal. And that's going to be your score for each parameter. Now, this doesn't seem too hard, right? You just need you don't even need a batch, you need a single data point, one back propagation, and then you get your scores. Okay, you don't need expensive training or anything like this. This seems pretty cool. And they give an example here. For example, for a simple, come on, for a simple fully connected network, ie this, so they consider here a linear network, right, just so we can look at exactly what happens for linear networks, you can often compute quantities exactly. So if we look at just a linear network without nonlinearities, we can factor the synaptic flow score for any parameter as such. So the score, this is now not the the R, this is going to be the score is going to be this thing right here. So you can see that the parameter is multiplied by this thing, and by this thing. And other than for example, magnitude pruning, this actually takes into account all the input flow because it goes from this one, sorry, it goes from this goes from this one, it goes through all the network, right, every path that arrives at this particular weight is going to be considered. And every path that goes out from this particular weight is going to be considered. And the saliency score is going to depend on all of these paths, all of these all of the information flow from input to output that goes through that weight. And if you do this, then you get a really good pruning algorithm. So yeah, the algorithm is is I've already described it. And in their experiments, as you can see right now, they have a bunch of networks, these VGG networks, or like wide resnet, they have a bunch of data sets like tiny image net or C for 10, where they experiment with these different baselines. And you can see that the baselines often run into this layer collapse problem. Sorry, often run into this where all of a sudden, let's actually look at let's look at this resonant 18. Right here. Maybe you can find a connection between maybe there's differently sized layers in resonant 18. And that's why the collapse happens even earlier. But you can see right here, there's a collapse if you do magnitude pruning, even also if you do random pruning, it falls down pretty hard after a while, the baselines they hold up better. But you can see in different models and different data sets, that the baselines crash at some point as well. Now I've already said the comparison here, it seems a little bit unfair. I might I might have over read something, but I'm pretty sure that the baselines remain single shot, while the sin flow algorithm here is now of course, no longer single shot, it's actually multi shot, and they've made the exact argument that the single shot is the problem. And therefore their algorithm is multi multi shot. And it it seems like they should give the other algorithms the opportunity to also do multi shot, just to compare them fairly. Maybe, as I said, maybe they're doing that, but I'm, I haven't read any anything. So it, you know, it just seems like the comparison is a bit unfair. If you identify the problem, and then just leave the other algorithms with the problem, sin flow is still different from these other algorithms, even if they had the multiple steps. Now, the counter argument to this, of course, is that these other algorithms all require the training data, they require actually passing the data or training the network in the case of magnitude pruning and so on. So that's pretty expensive, whereas sin flow, you simply pass forward one data point, and that's it. That's a good argument. But it seems like the effect of the synaptic saliency scores, and the effect of the multiple steps aren't really disentangled in these experiments right here, it simply shows that it consistently outperforms other pruning methods. And what what I'd like to see is really where that outperforming comes from. Okay, so that's what I think of this. And that was the paper, basically, I'm even even if I am not convinced quite yet. This is pretty cool, right? And I think this will, if not be if it's not used itself, it will inspire kind of a line of work into pruning at the beginning of training without looking at data. And maybe, you know, maybe we can even think of building networks, like, instead of just pruning them, we can think of constructively building networks that observe these properties. And therefore, we can just construct initialized networks already with good properties such that we don't even have to go to a bigger network and then prune it down. It seems wasteful. It seems like we should just be able to derive principles of what we want in the how the weights are structured, and then construct networks that are according to that. And I guess that's what's going to happen in a few papers that are coming. Alright, again, if you like this video, consider subscribing, giving it a like commenting, and let me know what you think. And until next time, bye bye.
 Hi there! Today we're looking at pruning neural networks without any data by iteratively conserving
 synaptic flow by Hidenori Tanaka, Daniel Kunin, Daniel L.K. Yamins and Surya Ganguly. So this
 paper on a high level does what the lottery ticket hypothesis does, but does so without
 any data. It prunes a neural network at the beginning and it does so. It's able to do
 that because it claims that its algorithm avoids this problem called layer collapse
 and then is based on conserving a quantity they call the synaptic flow. And we're going
 to look at this and it's a pretty cool algorithm. It seems to work pretty well. As always, if
 you want to help out, you can share this video and let me know in the comments what you think
 of it. I do read the comments and I would love to hear from you. Alright, let's dive
 in. So they're saying, pruning the parameters of deep neural networks has generated intense
 interest due to potential savings in time, memory and energy, both during training and
 at test time. Recent works have identified through an expensive sequence of training
 and pruning cycles, the existence of winning lottery tickets or sparse trainable sub networks
 at initialization. So what is this paper talking about? If you don't know much about pruning,
 here is kind of a basic overview. So if you have a neural network that consists of many,
 many layers of neurons, what you can do, that one way of pruning that, what the goal is,
 is to end up with a small neural network that performs well. But for now, we have a big
 neural network that doesn't perform well. It hasn't been trained yet, right? So what
 you can do is you can first train the neural network. And then you have a big neural network
 that performs well, and then you can prune it. Now, a lot of times, a lot of the time
 this has been seen as sort of the pruning way. You would train the big neural network
 and then you would prune it, because the other way was not feasible. First pruning and then
 training was not feasible. You might ask, okay, we might just want to start with a small
 one. And yeah, that's correct. So what does this first way buy you? This first way buys
 you mainly two things. So imagine this network right here is much smaller than the original
 network. So it is less, it uses less storage. So you can potentially, if you want to ship
 it to like a customer over the internet, you maybe instead of a gigabyte, you only have
 to transfer a few megabytes. And that's pretty cool. The second thing, if you prune in the
 correct way, you can also make it faster because now there's less weights to multiply with,
 you can actually make it go faster. So pruning is a now this this and it combines with techniques
 called distillation and so on is our ways to make the networks smaller and faster. So
 if your customers are for example, on on mobile phones, then you can ship you can train a big
 network to a good performance on your big GPU server, and then ship it out to a mobile
 phone. Once it's small, and it will perform fairly well on that mobile phone without GPU.
 So what about this other way? Now, in order to do the other way, we would sort of have
 to have an idea which one of these big networks which sub parts of these layers are the good
 ones, right in order for us to do this first prune and then train. The interesting thing
 is that the paper the lottery ticket hypothesis, I've done a video on this and we've also interviewed
 the author on our ML Street talk podcast. This paper has shown that this is in fact
 possible. A long time people have thought we need the big network in order to train,
 right? We sort of the bigness of the network, the full connectedness of the network is required
 for the training dynamics. But this paper has shown this is not possible, you can prune
 at the very beginning. Now, what does it do? It first trains a neural network, like in
 the olden days, then it prunes the neural network. And then it remembers which connections
 of the train neural network it has pruned. And then it simply goes back to the beginning
 of training right here, up here, and says, I now know which connections are important.
 And I'm simply going to prune all the other connections other than these ones. And then
 interestingly, if you prune first, and then train, that works just as well and can actually
 work even better. The interesting thing here is that I mean, this is a big, big cycle.
 But the interesting thing that the paper demonstrates is that this is even possible, right? People
 thought it wasn't possible. And this paper demonstrates if you only knew if you only
 knew which ones you must retain, you can prune at the beginning of training. The lottery
 ticket hypothesis paper, though still requires to actually train the full network and then
 do the pruning, like in a classic way in order to find out which ones you need to prune and
 which ones you don't. This paper right here takes that idea and says, can we find can
 we find a pruning algorithm that prunes at the beginning of training, yet does not have
 to train the full network, in fact, doesn't look at any of the data? Okay, and this is
 are going to be our starting point. So their story is going to be, it's quite an involved
 story. And I think the overview is important. Well, as we go through the paper. So first,
 they named this problem called layer collapse. Now, layer collapse is going to be whenever
 a pruning algorithm removes the entirety of a neural network layer, which means that no
 information can flow anymore. And therefore the network can't train. And they claim that
 this is the main problem, why these current pruning algorithms cannot achieve very high
 pruning ratios, so can like very high compression ratios is because they do premature layer
 collapse, they then formulate this maximal critical critical compression axiom that has
 sort of a guiding principle to build pruning algorithms. Second, they show that this quantity
 called synaptic saliency, a general class of gradient based scores for pruning is conserved
 at every hidden unit layer of a neural network. So they show that these are conserved. And
 they show this because this is their, their argument is going to be first, the argument
 is layer collapse is a problem. The second argument is these things are conserved and
 these, the conservation of the synaptic saliency leads to the layer collapse. And we're going
 to see how that happens. And then third, they say the solution to that is iterative pruning.
 So they show this at the at the example of iterative magnitude pruning, which we know
 avoids layer collapse. So iterative magnitude pruning is something that happens in this
 lottery ticket way of of doing it. This lottery ticket way, you can actually do it not in
 one step, but it tends to work better when you want to go from 100% of your weights to
 just 5% of your weights, it tends to work better if you do it in stages. So first you
 go to 90% to 80 to 70 and so on down to your desired thing. And this iterative procedure,
 they claim is what is what circumvents this problem of layer collapse. And then at last,
 they say we proved that a pruning algorithm avoids layer collapse entirely and satisfies
 blah blah blah, if it uses iterative positive synaptic saliency scores. So they bring it
 all together and say, if an algorithm satisfies our axiom, and if the algorithm is an algorithm
 that uses these saliency scores, like this one here, and if the algorithm is iterative,
 then it is not going to be subject to layer collapse. And therefore, it is going to be
 able to compress to a very high compression ratio. And then they actually do suggest an
 algorithm, this iterative synaptic flow pruning, SYNFLOW, that does all of this and never looks
 at any data. All right, this is quite a story. But remember what we're doing. First, layer
 collapse is a problem. Second, why is layer collapse a problem? It's because of this synaptic
 saliency conservation. Third, we can avoid it by doing iterative pruning. And lastly,
 this algorithm does it without looking at data. Okay, so layer, layer collapse, layer
 collapse is a pretty simple phenomenon. I've already said it, if you have a neural network,
 and it has a bunch of layers, and let's draw a couple of neurons here, and the neurons
 are connected to each other via connections, connections, connections, connections. And
 you have a pruning algorithm. Now the pruning algorithms they consider here are so called
 single shot pruning algorithms. What they do is they look at the neural network, and
 this can be before training or after training. But at some point, they look at the neural
 network, and they assign a score to each of these weights. Like they'll say, you're a
 one, you're a five, you're a nine, and so on. And then they simply prune away the lowest
 scores. Okay, and you tell the network what compression ratio you want to you tell the
 network, for example, please prune away 90% of the connections. So these algorithms would
 look would assign the scores once and then remove the bottom 90% of weights. Okay, like
 this. So those are the single shot pruning algorithms. Now what is layer collapse? Layer
 collapse is whenever an algorithm removes all of one layer, because maybe so here was
 a nine, maybe you have like 111213 here. Okay, so and then you're in you're in this situation
 right here. And the algorithm is pretty, is pretty dumb. It's simply removing the bottom
 90% of the connections. And here it figures I need to remove one more to meet that goal.
 I remove the one with the lowest score, I'm going to remove this one. And it's pretty obvious
 that now no more information can flow from the beginning to the end of the network because,
 well, what's where is it going to flow to? It's a bit more complex than that. Like, you
 can't just retain a layer like a connection. For example, if this were a connection, there
 would also be no information flow because you'd have no outgoing connection here. But
 ultimately, layer collapse is whenever an entire layer is removed. Okay. And they they
 do say somewhere that that's the case. I think layer collapse here, layer collapse occurs
 when an algorithm prunes all parameters in a single weight layer, even when prunable
 parameters remain elsewhere in the network. So I'm not as such, I'm not sure that this
 is like a giant problem. It gets to be a problem. But it could be circumvented fairly easily,
 right by simply saying, if you're about to prune a connection that's integral to the
 information flow from the start to the end, don't prune that connection, prune some other
 connection, right, and then you could simply avoid that. And I'd be interested in how that
 works out. So but in this case, for purposes of this paper, they simply consider algorithms
 that assign a score and then prune the bottom couple of percent, okay, for so we don't want
 any like handcrafted rules in here or something. So they look at this quantity called the max
 compression. The max compression is a quantity that's basically the maximum achievable compression
 while still avoiding layer collapse. And they say, for example, for a network with L layers
 and n parameters, the max compression is n over L, which is basically means every layer
 only has one parameter remaining and therefore, and if it's the correct one, therefore information
 can flow from start to the end. All right, so this is the maximum achievable compression,
 anything beyond that would automatically induce layer collapse. Now, anything before that
 could induce layer collapse, but there is a way to compress the network to the same
 level without inducing layer collapse. And their point is basically that these other
 compression algorithms that they compare with, they always they always induce layer collapse
 before they actually have to because they cut off a connection that leads to layer collapse
 before they like there would be another connection that they could cut off that would not lead
 to layer collapse. And of course, if you are layer, if you have done a layer collapse,
 then you accuracy immediately drops to zero or to random, because no more information
 flow. So they look at these things here, random pruning is where you simply assign a random
 score to each connection. Magnitude pruning is what the lottery ticket hypothesis does,
 but just they look here at a single shot. So you simply look at the magnitude of the
 weights and this can be before or after training. I think they do it after training here, which
 is classically done. You look at the magnitude of the weights and you prune the bottom 90%
 away. They there are also two more advanced methods, these SNIP and the grasp piece of
 SNIP and grasp, which look at the gradient of the training loss in the network and they
 decide according to that gradient, which which things to cut and which things not to cut
 away. The grasp even involves the Hessian right here. So they're fairly, you know, complex
 method that have some thoughts behind them about why they do what they do, yet they all
 induce layer collapse before they actually have to. So they define this thing here called
 the critical compression. The critical compression is the maximal compression ratio a given algorithm
 can achieve without inducing layer collapse. So the critical compression here is basically
 whenever that algorithm goes to zero, that's the critical compression. That's kind of the
 farthest you can push the algorithm without him without sorry, German speaker, without
 it induced without it inducing layer collapse. Okay, so you can see that for these baseline
 algorithms, the layer collapse occurs way below the theoretically possible max compression.
 And we're going to see that in their algorithm, this sin flow, that this max compression is
 achieved. And it's actually achieved without any of these handcrafted rules that I mentioned,
 it is the algorithm by design already achieved this maximum compression ratio. So they formulate
 this here as a guiding principle, they formulate as an axiom, I would, I would rather say it's
 like this kind of a, it's kind of a guiding principle of building these algorithms that
 any algorithm you build should have. So the critical compression ratio of a pruning algorithm
 applied to a network should always equal the max compression of that network. It basically
 means when you build a pruning algorithm, if you push that pruning algorithm to its
 limits, it should not do layer collapse unless it absolutely needs to. Okay. Again, the extent
 of this problem, I don't, I don't know, but they do demonstrate that that they can push
 their algorithm a fair bit further. Now, without inducing layer collapse, you already see that
 these other algorithms, like in this regime, apparently layer collapse hasn't happened
 yet because they still have sizeable accuracy, but there's still, you know, there is a reasonable
 difference here between those and the sin flow algorithm. So I'm not too convinced yet
 that layer collapse as such is the problem because they have a difference before their
 layer collapsing, as you can see right here. And I have the feeling that this difference
 here is due to this iterative procedure and not actually due to the phenomenon of layer
 collapse. But yeah, so if it were only layer collapse, what you'll see is that they do
 the same, the same, the same, and then at some point it's like, boom, now I have layer
 collapse. Okay. Yeah. So the layer collapse story, I'm not sure, but it's part of the
 story. So let's, let's go with that. The second part, which is kind of disconnected. So they
 established two things. They established a layer collapse problem, and now they establish
 the synaptic saliency, which then later they're going to connect to the layer collapse. So
 the synaptic saliency, they say is a score, is any score metric that can be expressed
 as the Hadamard product of this thing with the parameters. Okay. So each parameter is
 going to be multiplied by the gradient of some function with respect to that parameter.
 They say where R is a scalar loss function of the output of a feed forward neural network
 parameterized by theta. Okay. So many of these pruning algorithms can be formulated in this
 framework right here. And their, their algorithm can also be formulated in this framework.
 So you can see the score that the algorithm assigns to a weight can be defined as such.
 And as I said, many fall into this category or are similar to this, especially for example,
 they say when R is the training loss L. So this is the simplest case you take, you put
 data through the network, and then you take the training loss of that data and you sort
 of back propagate it. And now you're going to prune these connections according to how
 big the gradient is. If you say the gradient is very big, that must mean the connection
 is very important because there's lots of information flowing through it. So if it's
 a training loss L, the resulting synaptic saliency metric is equivalent to the score
 metric used in skeletonization, one of the first network pruning algorithms. The resulting
 metrics metric is also closely related to this right here. Now this you can see it's
 not exactly the same, but it's closely related to the one used in this snip baseline and
 also closely related to this thing right here used in grasp, where it's not just the gradient,
 it's actually the gradient multiplied by the Hessian to account for curvature. Okay, so
 they're going to investigate this synaptic saliency in neural networks. They formulate
 two theorems right here about the conservation of synaptic saliency. Remember synaptic saliency
 is any score that respects this that is built like this, any score S. The conservation of
 synaptic saliency, all synaptic saliency metrics respect two surprising conservation laws that
 hold at any initialization and step in training. So these are not usually like in distribution
 or something like this with high probability. These things hold at any point in the neural
 network. First is the neuron wise conservation of synaptic saliency. For a feet forward neural
 network with homogeneous activation functions and a homogeneous activation function is an
 activation function that can be expressed like this, for example, relu's fall into that
 category, the sum of the synaptic saliency for the incoming parameters is to a hidden
 neuron is equal to the sum of the synaptic saliency for the outgoing parameters from
 the hidden neuron. So what does it mean is actually pretty simple. If you have a hidden
 neuron and you look at all the incoming weights and you look at their synaptic saliency, which
 is this S score of each of these weights, like what would the pruning algorithm assign
 to that? And you look at the outgoing ones, then the sum of all the incoming ones is going
 to be equal to the sum of all the outgoing ones. So that's pretty interesting. And they
 extend that to layer to the entire network. So an extension of that network wise conservation
 of synaptic saliency, the sum of the synaptic saliency across any set of parameters that
 exactly separates the input neurons from the output neurons of a feet forward neural network
 with homogeneous activation functions equals that. So it basically says it remains equal.
 So what does it mean? What does it mean to exactly separate the input from the output?
 That's basically the definition of a layer in a neural network. So what they're saying
 is that you have a bunch of layers. And if you look at a particular layer like this one
 here, and you look at the incoming connections, and you sum up all of their synaptic saliency,
 that's going to be equal to the sum of all the synaptic saliency of the outgoing connections
 of that layer. And it can also apply to like a group of layers and so on. But the synaptic
 saliency is conserved in that way. Now, why is that important? And here is where we make
 the connection with the layer. Was it later drop layer? Whatever. Okay, the fact that
 the fact that these algorithms tend to drop entire layers before they have to, if you
 have in your network layers that are of different sizes, so you have large layers, and then
 smaller layers and smaller layers, what will happen is that since the synaptic saliency
 is conserved, the sum is conserved, if you have more connections in one layer, so lots
 of connections, lots of connections, and in the small layers, you don't have as many connections,
 the sum is equal. So that means each individual one here is much, much smaller. So the S is
 very small for each individual one here, and the S is very large in there. That means the
 pruning algorithm is going to really, really kill off these connections in the big layers.
 And it's actually going to kill them off to a point where it probably is going to eliminate
 that layer before it even prunes many of the connections of the small layer, just because
 of that conservation fact. And they do experiments like this. I think there's an experiment up
 here where I like this one down here better, where they basically show that you have inverse
 layer size on the bottom, and you have the average score that the pruning algorithm assigns
 to any connection. Now, these, as we've seen, they're not exactly assigning the scores of
 this saliency, but they're very close to it. The Synflow algorithm does exactly assign
 the synaptic saliency as the score for the pruning. Now, we've basically seen that this
 leads to a bad result, but the synaptic flow is going to compensate for that. But in essence,
 as you can see, as the layers get, so inverse layer size grows, which means that layer size
 shrinks as the layer size gets smaller, the average score of the connections in the layer
 is higher and higher, which basically means that the pruning algorithm, if you just let
 it go by itself, it's going to kill off the smaller, sorry, the larger layers first because
 they have the smaller scores. And you can see that even though the other algorithms
 don't conform exactly to that, they conform to this approximately. So these here, because
 their score is closely related to what the Synflow does, and the magnitude pruning, because
 mostly, because now I'm not sure if that's at the end of the training, at the beginning
 of the training, if you just initialize, then the score is going to be proportional to their
 magnitude and their magnitude is determined by the initialization scheme. And the initialization
 scheme is most of the time, like modern initialization schemes, compensate for the fact that you
 have different number of incoming and outgoing connections and therefore they would automatically
 assign a higher initialization constant to layers that have the lower number of parameters.
 So even the magnitude pruning will conform to this. Now, it might be absolutely reasonable
 to say that that's also the case at the end of training because most parameters aren't
 going to move super much during training. So this still approximately holds, as you
 can see here. Of course, the random one doesn't do that. Yet, because you prune randomly,
 you're still absolutely subject to this layer collapse. In fact, in the random one, the
 smallest layers would be the ones to go away first because it's just more probable. Okay.
 So we've discovered that if you do something like saliency scoring or something that's
 correlated to it, then you're going to remove the biggest layers first. And that's a problem.
 And that's what they say. This fact of this conservation laws and the single shot nature
 of these algorithms that they only assign scores once and then they prune away whatever
 the bottom such and such percent are leads to layer collapse. I think we've established
 this now that the combination of the two things leads to layer collapse. Now they make a little
 bit of an excursion and they say there is actually something that doesn't run into layer
 collapse. And that's iterative pruning algorithms. So specifically, they look at magnitude pruning.
 They say magnitude pruning, which remember is also if you do it single shot, it also
 runs into layer collapse. Magnitude pruning avoids layer collapse with conservation and
 iteration. So because it iterates, it avoids that. And that's what these lottery ticket
 hypothesis paper does. It does it iteratively removes a couple of connections, then it retrains
 the network, basically recomputes the magnitudes and therefore recomputes the scores. And then
 it prunes again, and then it recomputes and and prunes again. And by recomputing, you
 can basically these some of the connections that weren't important before, but just survive
 the pruning, they can now be like, wait, I have now way more responsibility as a connection,
 and they will shoot up in importance to avoid being pruned. So you can see if you push your
 network to a sorry to a high compression ratio, then if you just do this single shot pruning,
 you run into this layer collapse at some compression ratio, you simply crash to random performance
 or zero performance. Yet, if you do multiple iterations, you can see here already two iterations,
 then it's much longer before you run right here into layer collapse. And if you do three
 iterations, you do much more. Now this the three iterations doesn't mean you prune more
 like at this, at this point right here to tend to the one. All of these things prune
 nine out of every 10 connections. It's just the thing that has three iterations prunes
 maybe first three and then again, three and then again, three out of the 10. Whereas the
 one iteration would prune all of the nine at in one go. Okay. And they give a reason
 for this they give they say that it's the fact that gradient descent encourages conservation.
 So they give a little toy example here they say to better understand the dynamics of the
 IMP algorithm during training, the smaller we will consider the a differentiable score,
 this one. So this is not exactly magnitude pruning, but it is very close, right? The
 squared it's just the square of the parameter instead of the absolute value of the parameter.
 They say it's algorithmically equivalent to magnitude score. Consider these scores throughout
 training with gradient descent on a loss function using an infinitesimal step. In this setting,
 the temporal derivative of the parameters is equivalent to that. And thus the temporal
 derivative of the score is this. So now they're going to look at how does the score evolve
 when they train the network and the score evolves exactly as the negative to the saliency.
 Surprisingly, this is a form of synaptic saliency. And thus the neuron wise and layer wise conservation
 laws from section four apply. In particular, this implies that for any two layers of a
 simple fully connected network, then this quantity holds. So this is not new. But what
 it basically says is that through training, these connections equalize the saliency again.
 So if you have a very big layer, and here a very small layer, and because it's a big
 layer, these scores are very much lower, right? It's just little s and here it's big s per
 layer. But then if you prune away, and you run gradient descent on this, these scores
 will tend to become bigger. And in this case, these weights will tend to grow in magnitude.
 Because you've pruned away the others, they now have more signal probably flowing to them
 and more gradient flowing to them. And therefore they're going to grow in size. And therefore,
 their score is going to be bigger. So this gradient descent of this iterative procedure
 makes the scores better for that. So basically counteracts the layer collapse. So they put
 all of this together and say, theorem three, iterative positive conservative scoring achieves
 maximal critical compression. If a pruning algorithm with global masking, and global
 masking means that you rank all of the connections and then prune from all of the connections,
 it's a difference to layer wise masking where you say I want to remove 90% of each layer,
 which sounds like it would avoid layer collapse, but also it works a lot worse than the global
 one, the global strategy. Assigns positive scores that respect layer wise conservation.
 And if the algorithm, so respecting layer wise conservation, it basically means your
 score should be, or if your score is a saliency score, then that's the case. And if the algorithm
 reevaluates the scores every time a parameter is pruned, then the algorithm satisfies the
 maximal critical compression axiom. Okay. So that's basically saying that if you have
 any algorithm that prunes with a saliency score, like theirs is going to do, is going
 to be able to be pushed to the limit until the maximal capacity is reached if you reevaluate
 the scores every time a parameter is pruned. So this is basically saying that whatever
 the lottery ticket hypothesis paper did with magnitude pruning, if you do it with saliency
 based pruning, you're guaranteed to achieve the maximum possible compression if you push
 it. But of course we know that whatever the lottery ticket hypothesis paper did is impractical
 because it needs to retrain the network every single time it wants to prune. Right? So if
 you want to do this after every parameter, that's going to be a long time. It's going
 to be impractical. We ideally want to prune the network before we even look at any data.
 And they're going to do exactly that with the SYNFLOW algorithm. They say theorem three
 directly motivates the design of our novel pruning algorithm. SYNFLOW that provably reaches
 maximal critical compression. First, the necessity for iterative
 score evaluation discourages algorithms that involve back propagation on batches of data
 and instead motivates the development of an efficient data independent scoring procedure.
 Second, positivity and conservation probably motivates the construction of a loss function
 that yields positive synaptic saliency scores. We combine these insights and introduce a
 new loss function where the one is the all one vectors. Okay, so this is the loss function
 of their saliency scores. And this might seem like... So what do we have? We have the parameters
 of layer L, the absolute product, sorry, the absolute value of those parameters, and then
 you simply multiply all of the layers together. And you have this product here with the ones
 on the side. So this is a quadratic form, sort of. Okay, this might seem a bit weird,
 but in practice, and this is also what happens in their code, you can do something pretty
 easy. So first, you have to transform all your weights to their absolute values. Now
 in their code, you can look at it, they do remember the signs for later. So but first,
 you convert all of them to their absolute values. Then second, you simply take a data
 point that is filled with ones that literally the number one. So if your if your input is
 an image, you just put a one at each pixel, you feed it through the network with all of
 these positive weights, and you get out some output, you get some output vector, okay,
 then you simply you need to do this inner product with the one vector, which is simply
 a sum, right? I don't I don't get why they it's a bit of a funky way of writing a sum,
 right? You simply sum that up to get a to get a single number. And this single number
 now is your is your pseudo loss function. It's simply the loss function that an all
 one data point gets when the when the loss function is just the sum of the outputs. That's
 that's it. That's it. And then you back propagate that loss to you back propagate that loss
 to the layers. Right? So this is our remember this is not the score itself, but our score
 is going to be the derivative of our with respect to a weight times that weight. Okay,
 so you want to back propagate, and then you multiply each of these weights by the back
 propagated signal. And that's going to be your score for each parameter. Now, this doesn't
 seem too hard, right? You just need you don't even need a batch, you need a single data
 point, one back propagation, and then you get your scores. Okay, you don't need expensive
 training or anything like this. This seems pretty cool. And they give an example here.
 For example, for a simple, come on, for a simple fully connected network, ie this, so
 they consider here a linear network, right, just so we can look at exactly what happens
 for linear networks, you can often compute quantities exactly. So if we look at just
 a linear network without nonlinearities, we can factor the synaptic flow score for any
 parameter as such. So the score, this is now not the the R, this is going to be the score
 is going to be this thing right here. So you can see that the parameter is multiplied by
 this thing, and by this thing. And other than for example, magnitude pruning, this actually
 takes into account all the input flow because it goes from this one, sorry, it goes from
 this goes from this one, it goes through all the network, right, every path that arrives
 at this particular weight is going to be considered. And every path that goes out from this particular
 weight is going to be considered. And the saliency score is going to depend on all of
 these paths, all of these all of the information flow from input to output that goes through
 that weight. And if you do this, then you get a really good pruning algorithm. So yeah,
 the algorithm is is I've already described it. And in their experiments, as you can see
 right now, they have a bunch of networks, these VGG networks, or like wide resnet, they
 have a bunch of data sets like tiny image net or C for 10, where they experiment with
 these different baselines. And you can see that the baselines often run into this layer
 collapse problem. Sorry, often run into this where all of a sudden, let's actually look
 at let's look at this resonant 18. Right here. Maybe you can find a connection between maybe
 there's differently sized layers in resonant 18. And that's why the collapse happens even
 earlier. But you can see right here, there's a collapse if you do magnitude pruning, even
 also if you do random pruning, it falls down pretty hard after a while, the baselines they
 hold up better. But you can see in different models and different data sets, that the baselines
 crash at some point as well. Now I've already said the comparison here, it seems a little
 bit unfair. I might I might have over read something, but I'm pretty sure that the baselines
 remain single shot, while the sin flow algorithm here is now of course, no longer single shot,
 it's actually multi shot, and they've made the exact argument that the single shot is
 the problem. And therefore their algorithm is multi multi shot. And it it seems like
 they should give the other algorithms the opportunity to also do multi shot, just to
 compare them fairly. Maybe, as I said, maybe they're doing that, but I'm, I haven't read
 any anything. So it, you know, it just seems like the comparison is a bit unfair. If you
 identify the problem, and then just leave the other algorithms with the problem, sin
 flow is still different from these other algorithms, even if they had the multiple steps. Now,
 the counter argument to this, of course, is that these other algorithms all require the
 training data, they require actually passing the data or training the network in the case
 of magnitude pruning and so on. So that's pretty expensive, whereas sin flow, you simply
 pass forward one data point, and that's it. That's a good argument. But it seems like
 the effect of the synaptic saliency scores, and the effect of the multiple steps aren't
 really disentangled in these experiments right here, it simply shows that it consistently
 outperforms other pruning methods. And what what I'd like to see is really where that
 outperforming comes from. Okay, so that's what I think of this. And that was the paper,
 basically, I'm even even if I am not convinced quite yet. This is pretty cool, right? And
 I think this will, if not be if it's not used itself, it will inspire kind of a line of
 work into pruning at the beginning of training without looking at data. And maybe, you know,
 maybe we can even think of building networks, like, instead of just pruning them, we can
 think of constructively building networks that observe these properties. And therefore,
 we can just construct initialized networks already with good properties such that we
 don't even have to go to a bigger network and then prune it down. It seems wasteful.
 It seems like we should just be able to derive principles of what we want in the how the
 weights are structured, and then construct networks that are according to that. And I
 guess that's what's going to happen in a few papers that are coming. Alright, again, if
 you like this video, consider subscribing, giving it a like commenting, and let me know
 what you think. And until next time, bye bye.