Neural Architecture Search without Training (Paper Explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper nas nas-bench architecture search initialization untrained cifar10 imagenet neural architecture search controller rnn correlation gradient jacobian linearization
#ai #research #machinelearning

Neural Architecture Search is typically very slow and resource-intensive. A meta-controller has to train many hundreds or thousands of different models to find a suitable building plan. This paper proposes to use statistics of the Jacobian around data points to estimate the performance of proposed architectures at initialization. This method does not require training and speeds up NAS by orders of magnitude.

OUTLINE:
0:00 - Intro & Overview
0:50 - Neural Architecture Search
4:15 - Controller-based NAS
7:35 - Architecture Search Without Training
9:30 - Linearization Around Datapoints
14:10 - Linearization Statistics
19:00 - NAS-201 Benchmark
20:15 - Experiments
34:15 - Conclusion & Comments

Paper: https://arxiv.org/abs/2006.04647
Code: https://github.com/BayesWatch/nas-without-training

Abstract:
The time and effort involved in hand-designing deep neural networks is immense. This has prompted the development of Neural Architecture Search (NAS) techniques to automate this design. However, NAS algorithms tend to be extremely slow and expensive; they need to train vast numbers of candidate networks to inform the search process. This could be remedied if we could infer a network's trained accuracy from its initial state. In this work, we examine how the linear maps induced by data points correlate for untrained network architectures in the NAS-Bench-201 search space, and motivate how this can be used to give a measure of modelling flexibility which is highly indicative of a network's trained performance. We incorporate this measure into a simple algorithm that allows us to search for powerful networks without any training in a matter of seconds on a single GPU. Code to reproduce our experiments is available at this https URL.

Authors: Joseph Mellor, Jack Turner, Amos Storkey, Elliot J. Crowley


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
Parler: https://parler.com/profile/YannicKilcher
LinkedIn: https://www.linkedin.com/in/yannic-kilcher-488534136/

If you want to support me, the best thing to do is to share out the content :)

If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):
SubscribeStar (preferred to Patreon): https://www.subscribestar.com/yannickilcher
Patreon: https://www.patreon.com/yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n
 Hi there! Today we're looking at neural architecture search without training by Joseph Meller, Jack Turner, Alma Storky and Elliot J. Crowley. On a high level, this paper performs neural architecture search by looking at the correlation matrices of the Jacobian of the data when you pass it through the network. And it does so at initialization. So you pass the data, look at the Jacobian, and if it's very correlated, then the network is bad. And if it's very uncorrelated, then the network is good. And by simply observing that, they can already achieve a very good score on a neural architecture search benchmark. All right, that was a high level and maybe a bit too simplified. But that's sort of what's going on. Okay, let's dive in. So what's neural architecture search? Neural architecture search is the discipline of you are given a data set. Let's say here we have a data set, which could be something like CIFAR-10, which is an image data set. And you are given a sort of training procedure, let's say, ADM or SGD for 100,000 steps or something like this with many batches of size 64. Okay, and you're given a loss function, which the loss function here could be the cross entropy between the outputs of the network, which we'll call L and the label Y. And your task is now to find a neural network architecture that conforms to these specifications, but gives the lowest possible loss or the highest possible validation accuracy in this case. So this here would be like the train and then you'd have the test accuracy or the validation accuracy. Okay, so you could decide, well, I'm going to go with, you know, first, like three convolutional layers, each one having like a ReLU non-linearity. But you could also say, well, I'm going to build like a skip connection from here to here. You could also say that I'm going to down sample by two, you could have maybe a bigger stride and so on. So the kernel size of the convolution, you can vary until now, people have done this by hand, right? In effect, we all use like the same 10 to 20 different architectures. So if it's an image problem, we tend to go for like a ResNet or a wide ResNet, or like a VGG style architecture. Someone has come up with those at some point with each of those, discovered that it works well. And we don't really do much exploration, we simply kind of use the same things over and over. And the truth is that there might be much better architectures that we're simply not exploring, right? There might be much better building plans for networks that we don't know of that might perform a lot better with the same data and the same training. So neural architecture search is the process of automatically searching for these better architectures. Of course, that's a combinatorial problem. But the idea is that, you know, you can actually learn to construct good architectures. And by doing so, you can, you can sort of speed up this process that is manual otherwise. And the idea behind it is there's some regularity of when an architecture is good, there's some like high level pattern that you as a human maybe cannot really grasp, but like a machine can figure out which architectures are good and which ones aren't. So there have been a few inventions in this area, but they are mostly costly. That's what they say here. The time and effort involved in hand designing deep neural networks is immense. This has prompted the development of neural architecture search techniques to automate this design. However, neural architecture search algorithms tend to be extremely slow and expensive. They need to train vast numbers of candidate networks to inform the search process. So what neural architecture search methods do is what they'll have is they'll have something like a controller, the controller itself, of course, is going to be a neural network. So there'll be this thing that will be the controller, and the controller will emit like a building plan. So the controller will emit like a building plan for this network right here. And then you train the entire thing once through for the entire 100,000 steps. And then you observe the final validation accuracy, which might be something like 80%. And then you know, okay, this is 80%. So you feed the 80% into your controller and the controller outputs the next building plan that it thinks will score higher. And then you train the entire thing again, and you maybe observe 70% accuracy, you again feed that in, right, and the controller realizes, oh, I may have done something wrong, let me try something else. And does again, if this looks like reinforcement learning to you, that's because this is reinforcement learning. So the real the, the C here, the controller would be the agent, the percentages here, the accuracies would be the real reward. And the environment, the observations would be basically, this thing here, this thing would be the actions, but sometimes it's the observations and you need to score the different things. Okay. So the problem, of course, with this is that the reinforcement learning requires a lot of data, it requires a lot of steps to converge, because the signal from the reward is just so weak, you simply get one number for your action. And you don't know what you can change to make it better, you simply have to try. So you need a lot of steps, but this thing here is mighty slow, because each each single step in your reinforcement learning procedure involves training an entire neural network for like this many steps. Okay, so all of this is ginormously slow, and it's resource intensive. And that of course, blocks a lot of research, because, you know, we started with the plan to automate this part right here, but automating it itself is super expensive. So they go for a different solution. They say this could be remedied if we could infer at net, sorry, if we could infer a network's trained accuracy from its initial state. Okay, it seems a bit out there, but let's let's give them benefit of the doubt. In this work, we examine how the linear maps induced by data points correlate for untrained network architectures in the NAS bench 201 search space, and motivate how this can be used to give a measure of the accuracy of the network. So we use this measure to give a measure of modeling flexibility, which is highly indicative of a network's trained performance. We incorporate this measure into a simple algorithm that allows us to search for powerful networks without any training in a matter of seconds on a single GPU. Okay, and they have the code available right here if you want to go and check that out. So let's go ahead and check that out. The claims are pretty big. And the reasoning behind the claims is the following observation. You can already sort of see in this graphic right here, we'll go over what it means in one second. But what they do is they take different networks in this search space. And the search space in this case is given by this benchmark. So this benchmark basically has a long architectures that you could consider. Actually, so it's a constructive list. So they don't actually give you the list, but they give you like a way to construct architectures. And they took those architectures and they rank them by how well they score on CIFAR-10. So there are very good architectures, which are here, there are good ones, there are mediocre ones, and then the bad ones. Okay, and you can see that the histograms here of whatever they measure, they look quite different. So the histograms with the good ones, they all look kind of spiky around zero. And the histograms of the bad ones all sort of look spread out. So this is the measure that they're going to propose is they have some sort of number, some sort of histogram that they produce. And if the histogram is very spiky and close together around zero, then they conclude that this network is good. And if the histogram is very spread out like this, they conclude that the network is bad. Now these histograms, as you might expect, they are computed not from the final trained network, but they are computed from the initial network. So here they show at least, you know, in this case, it seems to be that there is a general correlation between the trained accuracy and how this histogram looks. And we're going to explore what they do. So it's essentially, it's pretty easy. They compute the linear map around each data point. So what is that? If you imagine a neural network as a nonlinear function, which I guess you should, because it is. And so let's imagine it as like a nonlinear function from X to Y. What they'll do is simply they'll look at a given date training data point, which could be here, right? This could be the X and this could be the Y. And in fact, let's look at it in loss landscape, not even in Y, but in L in terms of the loss, because we don't need necessarily a single label. This could be for unsupervised, this could be for anything. Okay, so it maps a data point to a loss. Now, what we'll do is we'll simply linearize the function around that point, which means we'll just freeze all the nonlinearities in place. And that will give us this linear function right here. Okay, we just observe that this linear function can exist. It's the tangent to the loss landscape. And it's at a particular data point, right? It's in data space, not in weight space. Then we look at a different data point. So we look at this data point right here, another data point. What's the linear function around this one is sort of like, whoops, D is like that. And then around this one is like this. Okay, so this is one function. Now let's look at a different function right here. So L, X, and we'll look at this function, the linear function. Okay, so for some reason, this is like this. And if we consider two data points, their linearization is very similar. Now imagine that these two have been produced by the same sort of neural networks. It's just the architecture is a little different. But they have the same number of parameters in the neural network. Which neural network would you prefer? Remember, by training the neural network, you can actually shape this loss function. You can kind of shape that around. So which one would you prefer? I personally would prefer the top one, because the top one already tells me that, hey, you know, I might have 10 parameters here. And this already sort of looks like each of the 10 parameters is doing something. So if I then go into my 10 parameters, and I, you know, turn this knob right here, then I might, you know, up this bump, or down this bump, or do something with it. But the sort of frequency, curvature, the randomness of the function, the way that it fluctuates tells me that all of the different parameters must have some sort of effect, right? Because it's quite an expressive function. Whereas if I have the same number of parameters for a function like this, this sort of tells me, well, maybe only one of the when the only one of the weights is actually doing something, maybe only one of the dimensions is doing something. This seems odd, right? That even though I've initialized it randomly, a super regular function like this comes out. So maybe all of the all of these parameters down here, they don't do anything. Or this, so somehow the signal doesn't get through. So that's, I, they don't explicitly say it in these terms. But this is how I make sense of this. What they're saying is that if you look at the linearizations of the functions, and you look at the the angle right here, so the angle in this case is that and in this case is that and in this case is that. So you look at the slope here. And the slope is basically the gradient of these linearized functions. And what you want to do is you want to look at the correlation between those of the different data points. So here we have three angles. One is very short, one is very bit longer, like this, and or no, even like this, and one is even over 90 degrees like that. They are not correlated at all, right? They're all very different. However, the angles here, they're all quite the same, as you can see. So what they propose is the following. Let's send all the data points, or in that case, all the data points in a particular mini batch, let's send them through the function, and let's calculate their linearizations. So the linearization is nothing else than you send them through the network to obtain the f value for the x value, and then you calculate the gradient with respect to the input. Now you have to get used to this a bit, because usually we calculate the gradient with respect to the weight. So you calculate the gradient, but now we calculate the gradient with respect to the input, which if this is a linear function, so if you have a f of x equals wx, like a linear function, then this gradient, del f del x, would just give you the w, will give you the slope of the linear function, and the same in the neural network when you linearize it. All right, so we're going to obtain all these linearizations, and that gives us this matrix J right here. And what we can do is we can then observe the covariance matrix of J, of all these linearizations. The covariance matrix simply tells you how two data points vary with each other, and in fact they don't look at the covariance matrix, but they look at the correlation matrix, which is simply the scaled covariance matrix. So one entry in this covariance matrix, so you have n data points, and this gives you a matrix that's n by n, and a particular entry here, like the entry i, j, would simply state how does the angle of data point i correlate with the angle of data point j. Okay, that's the covariance matrix. And now the hypothesis is, if all of these data points are sort of independent, like in our very expressive function here, then these correlations, they should not be high. In fact most data points should be rather uncorrelated. However, in this case right here, if the function is sort of kind of degenerative or something, not very expressive, then all of these angles, all of these linearizations should be highly correlated. And that's what you see in this graph right here. This right here now is this correlation histogram of the correlations between local linear maps across all pairs of items in a mini batch of C410 training data. Each policy is scrammed for a single untrained NASBench 201 architecture. So remember the expressivity is important because we want to train that function, and therefore it's important that every parameter does something. And if it's degenerate, we can't train it well. And that's, I find that's the reasoning. They sort of say this, but I might make the wrong sense out of it here, but it seems to me like that's what's actually going on. So you can see this is simply these matrix values rolled out and then plotted as a histogram. So what does it mean when an histogram is like super spread out like this? It means that there are a lot, and I think down here are axes, yes, there are a lot of data points that correlate highly or anti-correlate highly with each other. Okay, which means that exactly this degeneracy happens. So either too high or too negative high correlation means that they're very much, they're kind of the same thing. So there is, if you have as many parameters as data points, that means that one parameter can potentially serve these two data points or these two that are correlated by one or negative one. You don't need both parameters and therefore you have a lot of parameters doing nothing. Whereas over here with the good networks, you can see that this spikes around zero, meaning that the data points are not correlated or the linearizations around the data points are not correlated. And therefore you can sort of shape the function around each data point however you want. Which we sort of know that neural networks, what they do is they're so over expressive that they're actually able to shape the functions around the data points without necessarily looking at other data points nearby. And that expressivity is what you want and that expressivity is what this in part measures. Okay, so they make a, they have some experiments here where they validate this. So for all these architectures in this benchmark, and maybe I should tell you what, show you what the benchmark looks like. So the benchmark has this particular form, this particular form, there's this skeleton, and in this skeleton there is this block and it's always repeated. And you're basically, your task is to determine what this block should be. So this block has an input node A and an output node D and two intermediate nodes. And what you have to do is basically you have to determine these connections right here. So there are six connections and for each one you have the option of putting different things there. Like you can see you can put a convolution, you can put the identity function, which is a skip connection, zero wise. I don't, maybe that's the zero function, so it basically means nothing. I'm not so sure, honestly. But you could technically put a convolution here and here, right, or different convolutions or things like this. So there are these 15,625 possible cells. So the NAS benchmark contains 15,625 possible architectures that you'll have to search. And they take these architectures and they plot now, they plot for each architecture the validation accuracy after training. And the training protocol is standardized, you don't have to care about that. And the score that they measure at the beginning of training. And what you can see is that there is a linear relationship, sort of, like sort of. From these experiments what you'll get is like this sort of feeling. What they're going to propose is that you should take that score as a measure. And here again also, sort of, sort of. There is a clear trend, as you can see, right here. Though, yeah, though this, as you can see, this sort of spreads out. And the most right one is ImageNet, which is the most difficult one, of course. So, and this is CIFAR 100, which is more difficult than CIFAR 10. So we can see that this sort of relationship at the top, it doesn't really hold anymore if the task gets difficult. And this is, so what I think is happening, this is kind of an interjection of my own opinion. What's happening here is that this score that they discover allows them pretty efficiently to see which networks are just degenerate and cannot be trained. Like if you try to train them, they just perform really poorly, okay? That, it's probably a very good score for weeding those out. And that would mean if you kind of barrier here somewhere, right? You could just discard a whole lot of this crap, or even here, right? You could just discard a whole lot of this crap. And also now here, just, you know, all of this crap. Yeah, whereas here, as you can see, some, this score, sometimes it's higher than these ones, even though they perform better. And again, you could probably discard a lot of the crap, but it's not as distinctive for the well performing networks, because these here are all not the degenerate version, right? They're not degenerate in the sense that they're, they have some fundamental flaw where the function lacks now expressivity from the very start, so you can't train it. And so, you know, it's not a big deal. And then probably other factors come into play, other factors than you can simply determine with this particular score. But, you know, there is this relationship that's, you know, you can see that. And they do some ablations on this here. For example, are your scores a proxy for a number of parameters? And they say, no, the number of parameters works way than this particular score, which, you know, is a cool thing. Then how important is the specific mini batch and initialization? And they say, look right here, we, for some architectures, we do different mini batch sizes. And you can see each of those groups, they don't vary too much in how they're, it influences their score. This is, I believe this is the same architecture. So it's always an architecture that achieves in this case, for example, wow, that's not a straight line, 77% or so. And you can see if you go for different mini batches, the score varies only minimally. Initialization is a bigger variance inducing thing. But also here, the scores don't vary too much. But it is interesting that the different initialization do get you to different score, because it would directly support kind of my hypothesis that what's going on here is that you sort of measure initial degeneracies. And you can sort of make up for these initial degeneracies in the architecture sometimes with sort of a different initialization. So the different initializations give you differently performing networks. We already know this from things like, you know, lottery ticket hypothesis and so on, that the initialization can matter to some degree in these types of things. Now, that being said, they always train to the same, it seems, but their their score varies. So I might be backwards correct here, or not correct. But in any case, the initialization here matters more, but also you can still see this linear relationship. And this is particularly interesting. This is even the case when you just input white noise. So instead of the data, you measure that score by just inputting noise that I guess has some sort of the same magnitude as the data would have, but it's just noise. And you can still sort of see this linear relationship, which is very interesting. And that I think also shows some that you what you're fine, what you find is a property of the network itself. And the fact that it is, it is initialized and built in such a way that it allows you to train it in a very, in a sort of a benign manner, it has no degeneracies. Okay. So in the last experiment, they go here and they say, we evaluated the score on initialized networks in the PyTorch CV library. So they go to this library that has a lot of these networks, but these networks are not the same as this benchmark. This benchmark is specifically designed to do architecture search. Now the networks in this library, they are all designed to perform really well. Some are designed to be quite small, some are designed to be quite fast and so on. But in general, they are all of their goal is to perform well, and they have been sort of found by humans to perform well. So they take now these networks on CIFAR 10 and they test them. So as you can see here, here is the test accuracy again, and here is their score that they give it. And they say, now I can't move this anymore. Hello. Well, okay. They say that this linear relationship still sort of holds. It doesn't hold super, super well, but you can still sort of, if you squint, if you squint hard, you can see that it sort of goes upward, though you really have to squint hard. Like what are these things right here? And what, again, what's the case is that if the score is low, it's not going to be a good score. So what you can do is that if the score is low, you will sort of be able to cut off the worst performing ones. But really at the top here, it doesn't seem like there is a particular relation between these networks and this initial score, which sort of strengthens my hypothesis that it's just kind of weed out the bad ones. But it's pretty cool because you can weed out the bad ones without any training, right? You'd simply forward prop backward prop. There you have it. So cool. Now they come, they, here is the experiment where they now really do this NAS benchmark and they compare with other methods. So some of these other methods are designed to do the call weight sharing, which basically is a technique where you can sort of speed up the speed up the algorithm as compared to non weight sharing and the non weight sharing. That's one of these we have discussed initially. That was my initial example with the controller and so on where it takes super long. So here you see the method and how long each method takes. Now the best ones, as you can see already, the best ones here, or these, these methods right here are the best ones. They score somewhat like a 93.9 or so on C for 10, whereas these weight sharing ones, they don't perform too well, except this one seems to perform quite well. And in this hours case, they perform worse than that, but they still perform better than a lot of the weight sharing ones. So what their point is basically is that they get a pretty good score, which is a 91.5 on C for 10, which is, you know, it's at least not degenerate. It's a, it's a good accuracy. They score that with simply evaluating 10 architectures, right? And as n goes up, as they evaluate more and more architectures, they do, they do get better, but not much. So they have a discussion here. I'm having trouble moving this. All right, so we'll sort of go through the discussion. We report results, yada, yada, yada, yada, yada. As the setup, the non weight sharing methods are given a time budget of 12,000 seconds for our method and the non weight sharing methods are averaged. Accuracies are averaged over 500 runs for weight sharing methods. Accuracies are reported over three runs with the exception of G Das. Our method is able to outperform all the weight sharing methods while requiring a fraction of the search time. And that you may see at the table. This is the real, I mean, this is the real deal here. They only use here 1.7 seconds compared to the 12,000 seconds of the other methods. And you reach almost the same accuracy. Now to be said, 2% in this particular regime on C410 is still a sizable difference. And that's the same benchmark, right? With the same sort of the same training schedule and so on. So there's not too much room to tune here. You simply have to find a better architecture. So these things are still sizably ahead of this. And what it appears to me that these methods here that don't perform well, they're simply crap. It seems they're simply, I don't know, but they might be trying out something or, you know, doing something researchy or whatnot. But it seems like if you're well able to weed out the bad architectures, you might be getting to a score like this. And then if you are actually performing a search to find the best one, then you might be getting to somewhere like this. And you can see this here throughout. So in C4100, they achieve a better score than these things, but a worse score than the non-weight sharing method. And in ImageNet, the difference is even larger. So again, what I can see here is that theirs is a good method to maybe get you, let's say, 90% of the way you want to go. And what's interesting is that here they say, we also show the effect of sample size. We show the accuracy of the networks chosen by our method for each n. So that's the sample size. We list the optimal accuracy for sample sizes 10 and 100 and random selection over the whole benchmark. So in this case, they have the optimal one, which I guess they just draw 10 samples and then take the best one. So they train all of them and then take the best one. And you can see that already gets you to the 93. And whereas in their case, sometimes when they add more, they get worse. So here they get better, but then they get worse again. So they comment on this right here. We observe that the sample size does not have a large effect on the accuracy of our method. But note that as sample size increases, our method suffers from a small amount of noise, increasing the gap between our score and the optimal result. And of course, the key practical benefit is execution time. So again, they are massively faster than the other methods. But to me, it seems you could just think of combining these methods, right? You combine this with this in that what you want to do is actually actively search for the best ones. But by doing so, you could, if you could pretty quickly weed out the bad ones using this method down here, you might already have like a big speed up. Because again, with comparison to this random ones, what appears to happen is that they get good at finding, you know, your 90% architecture, but then they fail to differentiate the top performance performers from each other, where you'd really have to train the network to find out what's, you know, which one's better. So yeah, here they say they visualize the trade off between search time and accuracy for C410 for different NAS algorithms on the NAS benchmark. By removing the need for training, our method is able to find accurate networks in seconds instead of hours. And here you can see the accuracy and here you can see the time and all the good ones are either way over here or here. And theirs is almost at zero while being quite close to the accuracy of the other ones. All right, yeah, that was that was this paper. Again, I think this is pretty valuable if you are especially if you're in a new domain, where you might not know what kind of network to build, you might just be able to write a little script that generates networks, run it through this algorithm, and at least you get an idea of which ones are certainly not worth considering. And then you can simply select one of the other ones. It doesn't, you know, often it doesn't need to be the best ones. And you can then tweak it a little bit manually, the ones you found, maybe you see some regularity. And yeah, that was my two cents on this paper. I hope you liked it. If you did, consider sharing it out and telling your friends about it and subscribing, liking, and leave a comment if you agree or disagree. That was it. Bye bye.
 Hi there! Today we're looking at neural architecture search without training by Joseph Meller, Jack
 Turner, Alma Storky and Elliot J. Crowley. On a high level, this paper performs neural
 architecture search by looking at the correlation matrices of the Jacobian of the data when
 you pass it through the network. And it does so at initialization. So you pass the data,
 look at the Jacobian, and if it's very correlated, then the network is bad. And if it's very
 uncorrelated, then the network is good. And by simply observing that, they can already
 achieve a very good score on a neural architecture search benchmark. All right, that was a high
 level and maybe a bit too simplified. But that's sort of what's going on. Okay, let's dive in.
 So what's neural architecture search? Neural architecture search is the discipline of you
 are given a data set. Let's say here we have a data set, which could be something like CIFAR-10,
 which is an image data set. And you are given a sort of training procedure, let's say, ADM or SGD
 for 100,000 steps or something like this with many batches of size 64. Okay, and you're given a loss
 function, which the loss function here could be the cross entropy between the outputs of the network,
 which we'll call L and the label Y. And your task is now to find a neural network architecture
 that conforms to these specifications, but gives the lowest possible loss or the highest possible
 validation accuracy in this case. So this here would be like the train and then you'd have the
 test accuracy or the validation accuracy. Okay, so you could decide, well, I'm going to go with,
 you know, first, like three convolutional layers, each one having like a ReLU non-linearity.
 But you could also say, well, I'm going to build like a skip connection from here to here.
 You could also say that I'm going to down sample by two, you could have maybe a bigger stride and
 so on. So the kernel size of the convolution, you can vary until now, people have done this by hand,
 right? In effect, we all use like the same 10 to 20 different architectures. So if it's an image
 problem, we tend to go for like a ResNet or a wide ResNet, or like a VGG style architecture.
 Someone has come up with those at some point with each of those, discovered that it works well.
 And we don't really do much exploration, we simply kind of use the same things over and over.
 And the truth is that there might be much better architectures that we're simply not exploring,
 right? There might be much better building plans for networks that we don't know of that might
 perform a lot better with the same data and the same training. So neural architecture search is
 the process of automatically searching for these better architectures. Of course, that's a
 combinatorial problem. But the idea is that, you know, you can actually learn to construct good
 architectures. And by doing so, you can, you can sort of speed up this process that is manual
 otherwise. And the idea behind it is there's some regularity of when an architecture is good,
 there's some like high level pattern that you as a human maybe cannot really grasp, but like a
 machine can figure out which architectures are good and which ones aren't. So there have been a few
 inventions in this area, but they are mostly costly. That's what they say here. The time and
 effort involved in hand designing deep neural networks is immense. This has prompted the
 development of neural architecture search techniques to automate this design. However,
 neural architecture search algorithms tend to be extremely slow and expensive. They need to train
 vast numbers of candidate networks to inform the search process. So what neural architecture
 search methods do is what they'll have is they'll have something like a controller,
 the controller itself, of course, is going to be a neural network. So there'll be this thing that
 will be the controller, and the controller will emit like a building plan. So the controller will
 emit like a building plan for this network right here. And then you train the entire thing once
 through for the entire 100,000 steps. And then you observe the final validation accuracy, which
 might be something like 80%. And then you know, okay, this is 80%. So you feed the 80% into your
 controller and the controller outputs the next building plan that it thinks will score higher.
 And then you train the entire thing again, and you maybe observe 70% accuracy, you again feed
 that in, right, and the controller realizes, oh, I may have done something wrong, let me try
 something else. And does again, if this looks like reinforcement learning to you, that's because
 this is reinforcement learning. So the real the, the C here, the controller would be the agent,
 the percentages here, the accuracies would be the real
 reward. And the environment, the observations would be basically, this thing here, this thing
 would be the actions, but sometimes it's the observations and you need to score the different
 things. Okay. So the problem, of course, with this is that the reinforcement learning requires a lot
 of data, it requires a lot of steps to converge, because the signal from the reward is just so
 weak, you simply get one number for your action. And you don't know what you can change to make it
 better, you simply have to try. So you need a lot of steps, but this thing here is mighty slow,
 because each each single step in your reinforcement learning procedure involves training an entire
 neural network for like this many steps. Okay, so all of this is ginormously slow, and it's
 resource intensive. And that of course, blocks a lot of research, because, you know, we started
 with the plan to automate this part right here, but automating it itself is super expensive.
 So they go for a different solution. They say this could be remedied if we could infer at net,
 sorry, if we could infer a network's trained accuracy from its initial state. Okay, it seems
 a bit out there, but let's let's give them benefit of the doubt. In this work, we examine how the
 linear maps induced by data points correlate for untrained network architectures in the NAS bench
 201 search space, and motivate how this can be used to give a measure of the accuracy of the
 network. So we use this measure to give a measure of modeling flexibility, which is highly indicative
 of a network's trained performance. We incorporate this measure into a simple algorithm that allows
 us to search for powerful networks without any training in a matter of seconds on a single GPU.
 Okay, and they have the code available right here if you want to go and check that out. So let's go
 ahead and check that out. The claims are pretty big. And the reasoning behind the claims is the
 following observation. You can already sort of see in this graphic right here, we'll go over what it
 means in one second. But what they do is they take different networks in this search space. And the
 search space in this case is given by this benchmark. So this benchmark basically has a long
 architectures that you could consider. Actually, so it's a constructive list. So they don't actually
 give you the list, but they give you like a way to construct architectures. And they took those
 architectures and they rank them by how well they score on CIFAR-10. So there are very good
 architectures, which are here, there are good ones, there are mediocre ones, and then the bad ones.
 Okay, and you can see that the histograms here of whatever they measure, they look quite different.
 So the histograms with the good ones, they all look kind of spiky around zero. And the histograms
 of the bad ones all sort of look spread out. So this is the measure that they're going to propose
 is they have some sort of number, some sort of histogram that they produce. And if the histogram
 is very spiky and close together around zero, then they conclude that this network is good.
 And if the histogram is very spread out like this, they conclude that the network is bad. Now these
 histograms, as you might expect, they are computed not from the final trained network, but they are
 computed from the initial network. So here they show at least, you know, in this case, it seems
 to be that there is a general correlation between the trained accuracy and how this histogram looks.
 And we're going to explore what they do.
 So it's essentially, it's pretty easy. They compute the linear map around each data point.
 So what is that? If you imagine a neural network as a nonlinear function, which I guess you should,
 because it is. And so let's imagine it as like a nonlinear function from X to Y. What they'll do
 is simply they'll look at a given date training data point, which could be here, right? This could
 be the X and this could be the Y. And in fact, let's look at it in loss landscape, not even in Y,
 but in L in terms of the loss, because we don't need necessarily a single label. This could be
 for unsupervised, this could be for anything. Okay, so it maps a data point to a loss. Now,
 what we'll do is we'll simply linearize the function around that point, which means we'll
 just freeze all the nonlinearities in place. And that will give us this linear function right here.
 Okay, we just observe that this linear function can exist. It's the tangent to the loss landscape.
 And it's at a particular data point, right? It's in data space, not in weight space. Then we look
 at a different data point. So we look at this data point right here, another data point. What's the
 linear function around this one is sort of like, whoops, D is like that. And then around this one
 is like this. Okay, so this is one function. Now let's look at a different function right here. So
 L, X, and we'll look at this function, the linear function. Okay, so for some reason,
 this is like this. And if we consider two data points, their linearization is very similar.
 Now imagine that these two have been produced by the same sort of neural networks. It's just
 the architecture is a little different. But they have the same number of parameters in the neural
 network. Which neural network would you prefer? Remember, by training the neural network, you can
 actually shape this loss function. You can kind of shape that around. So which one would you prefer?
 I personally would prefer the top one, because the top one already tells me that, hey, you know,
 I might have 10 parameters here. And this already sort of looks like each of the 10 parameters is
 doing something. So if I then go into my 10 parameters, and I, you know, turn this knob
 right here, then I might, you know, up this bump, or down this bump, or do something with it. But
 the sort of frequency, curvature, the randomness of the function, the way that it fluctuates tells
 me that all of the different parameters must have some sort of effect, right? Because it's quite an
 expressive function. Whereas if I have the same number of parameters for a function like this,
 this sort of tells me, well, maybe only one of the when the only one of the weights is actually
 doing something, maybe only one of the dimensions is doing something. This seems odd, right? That
 even though I've initialized it randomly, a super regular function like this comes out. So maybe all
 of the all of these parameters down here, they don't do anything. Or this, so somehow the signal
 doesn't get through. So that's, I, they don't explicitly say it in these terms. But this is
 how I make sense of this. What they're saying is that if you look at the linearizations of the
 functions, and you look at the the angle right here, so the angle in this case is that and in
 this case is that and in this case is that. So you look at the slope here. And the slope is basically
 the gradient of these linearized functions. And what you want to do is you want to look at the
 correlation between those of the different data points. So here we have three angles. One is
 very short, one is very bit longer, like this, and or no, even like this, and one is even over
 90 degrees like that. They are not correlated at all, right? They're all very different. However,
 the angles here, they're all quite the same, as you can see. So what they propose is the following.
 Let's send all the data points, or in that case, all the data points in a particular mini batch,
 let's send them through the function, and let's calculate their linearizations. So the linearization
 is nothing else than you send them through the network to obtain the f value for the x value,
 and then you calculate the gradient with respect to the input. Now you have to get used to this a
 bit, because usually we calculate the gradient with respect to the weight. So you calculate the
 gradient, but now we calculate the gradient with respect to the input, which if this is a linear
 function, so if you have a f of x equals wx, like a linear function, then this gradient, del f del
 x, would just give you the w, will give you the slope of the linear function, and the same in the
 neural network when you linearize it. All right, so we're going to obtain all these linearizations,
 and that gives us this matrix J right here. And what we can do is we can then observe the
 covariance matrix of J, of all these linearizations. The covariance matrix simply tells you how two data
 points vary with each other, and in fact they don't look at the covariance matrix, but they look at the
 correlation matrix, which is simply the scaled covariance matrix. So one entry in this covariance
 matrix, so you have n data points, and this gives you a matrix that's n by n, and a particular entry
 here, like the entry i, j, would simply state how does the angle of data point i correlate with the
 angle of data point j. Okay, that's the covariance matrix. And now the hypothesis is, if all of these
 data points are sort of independent, like in our very expressive function here, then these correlations,
 they should not be high. In fact most data points should be rather uncorrelated. However, in this
 case right here, if the function is sort of kind of degenerative or something, not very expressive,
 then all of these angles, all of these linearizations should be highly correlated.
 And that's what you see in this graph right here. This right here now is this correlation histogram
 of the correlations between local linear maps across all pairs of items in a mini batch of C410
 training data. Each policy is scrammed for a single untrained NASBench 201 architecture. So remember
 the expressivity is important because we want to train that function, and therefore it's important
 that every parameter does something. And if it's degenerate, we can't train it well. And that's,
 I find that's the reasoning. They sort of say this, but I might make the wrong sense out of it here,
 but it seems to me like that's what's actually going on. So you can see this is simply these
 matrix values rolled out and then plotted as a histogram. So what does it mean when an histogram
 is like super spread out like this? It means that there are a lot, and I think down here are axes,
 yes, there are a lot of data points that correlate highly or anti-correlate highly with each other.
 Okay, which means that exactly this degeneracy happens. So either too high or too negative high
 correlation means that they're very much, they're kind of the same thing. So there is, if you have
 as many parameters as data points, that means that one parameter can potentially serve these two data
 points or these two that are correlated by one or negative one. You don't need both parameters and
 therefore you have a lot of parameters doing nothing. Whereas over here with the good networks,
 you can see that this spikes around zero, meaning that the data points are not correlated
 or the linearizations around the data points are not correlated. And therefore you can sort of shape
 the function around each data point however you want. Which we sort of know that neural networks,
 what they do is they're so over expressive that they're actually able to shape the functions
 around the data points without necessarily looking at other data points nearby. And that
 expressivity is what you want and that expressivity is what this in part measures. Okay, so they make
 a, they have some experiments here where they validate this. So for all these architectures
 in this benchmark, and maybe I should tell you what, show you what the benchmark looks like.
 So the benchmark has this particular form, this particular form, there's this skeleton,
 and in this skeleton there is this block and it's always repeated. And you're basically,
 your task is to determine what this block should be. So this block has an input node A and an output
 node D and two intermediate nodes. And what you have to do is basically you have to determine
 these connections right here. So there are six connections and for each one you have the option
 of putting different things there. Like you can see you can put a convolution, you can put the
 identity function, which is a skip connection, zero wise. I don't, maybe that's the zero function,
 so it basically means nothing. I'm not so sure, honestly. But you could technically put a
 convolution here and here, right, or different convolutions or things like this. So there are
 these 15,625 possible cells. So the NAS benchmark contains 15,625 possible architectures that you'll
 have to search. And they take these architectures and they plot now, they plot for each architecture
 the validation accuracy after training. And the training protocol is standardized, you don't have
 to care about that. And the score that they measure at the beginning of training. And what you can see
 is that there is a linear relationship, sort of, like sort of. From these experiments what you'll
 get is like this sort of feeling. What they're going to propose is that you should take that score
 as a measure. And here again also, sort of, sort of. There is a clear trend, as you can see,
 right here. Though, yeah, though this, as you can see, this sort of spreads out. And the most right
 one is ImageNet, which is the most difficult one, of course. So, and this is CIFAR 100, which is more
 difficult than CIFAR 10. So we can see that this sort of relationship at the top, it doesn't really
 hold anymore if the task gets difficult. And this is, so what I think is happening, this is kind of
 an interjection of my own opinion. What's happening here is that this score that they discover
 allows them pretty efficiently to see which networks are just degenerate and cannot be trained.
 Like if you try to train them, they just perform really poorly, okay? That, it's probably a very
 good score for weeding those out. And that would mean if you kind of barrier here somewhere, right?
 You could just discard a whole lot of this crap, or even here, right? You could just discard a
 whole lot of this crap. And also now here, just, you know, all of this crap. Yeah, whereas here,
 as you can see, some, this score, sometimes it's higher than these ones, even though they perform
 better. And again, you could probably discard a lot of the crap, but it's not as distinctive for
 the well performing networks, because these here are all not the degenerate version, right? They're
 not degenerate in the sense that they're, they have some fundamental flaw where the function lacks
 now expressivity from the very start, so you can't train it. And so, you know, it's not
 a big deal. And then probably other factors come into play, other factors than you can simply
 determine with this particular score. But, you know, there is this relationship that's,
 you know, you can see that. And they do some ablations on this here. For example, are your
 scores a proxy for a number of parameters? And they say, no, the number of parameters works way
 than this particular score, which, you know, is a cool thing. Then how important is the specific
 mini batch and initialization? And they say, look right here, we, for some architectures,
 we do different mini batch sizes. And you can see each of those groups, they don't vary too much
 in how they're, it influences their score. This is, I believe this is the same architecture. So
 it's always an architecture that achieves in this case, for example, wow, that's not a straight line,
 77% or so. And you can see if you go for different mini batches, the score varies only minimally.
 Initialization is a bigger variance inducing thing. But also here, the scores don't vary too much.
 But it is interesting that the different initialization do get you to different score,
 because it would directly support kind of my hypothesis that what's going on here is that
 you sort of measure initial degeneracies. And you can sort of make up for these initial degeneracies
 in the architecture sometimes with sort of a different initialization. So the different
 initializations give you differently performing networks. We already know this from things like,
 you know, lottery ticket hypothesis and so on, that the initialization can matter to some degree
 in these types of things. Now, that being said, they always train to the same, it seems, but their
 their score varies. So I might be backwards correct here, or not correct. But in any case,
 the initialization here matters more, but also you can still see this linear relationship.
 And this is particularly interesting. This is even the case when you just input white noise. So
 instead of the data, you measure that score by just inputting noise that I guess has some sort
 of the same magnitude as the data would have, but it's just noise. And you can still sort of see this
 linear relationship, which is very interesting. And that I think also shows some that you what
 you're fine, what you find is a property of the network itself. And the fact that it is,
 it is initialized and built in such a way that it allows you to train it in a very,
 in a sort of a benign manner, it has no degeneracies. Okay. So in the last experiment,
 they go here and they say, we evaluated the score on initialized networks in the PyTorch CV library.
 So they go to this library that has a lot of these networks, but these networks are not the same as
 this benchmark. This benchmark is specifically designed to do architecture search. Now the
 networks in this library, they are all designed to perform really well. Some are designed to be
 quite small, some are designed to be quite fast and so on. But in general, they are all of their
 goal is to perform well, and they have been sort of found by humans to perform well. So they take
 now these networks on CIFAR 10 and they test them. So as you can see here, here is the test
 accuracy again, and here is their score that they give it. And they say, now I can't move this anymore.
 Hello. Well, okay.
 They say that this linear relationship still sort of holds. It doesn't hold super, super well,
 but you can still sort of, if you squint, if you squint hard, you can see that it sort of goes
 upward, though you really have to squint hard. Like what are these things right here? And what,
 again, what's the case is that if the score is low, it's not going to be a good score.
 So what you can do is that if the score is low, you will sort of be able to cut off the worst
 performing ones. But really at the top here, it doesn't seem like there is a particular relation
 between these networks and this initial score, which sort of strengthens my hypothesis that
 it's just kind of weed out the bad ones. But it's pretty cool because you can weed out the bad ones
 without any training, right? You'd simply forward prop backward prop. There you have it. So cool.
 Now they come, they, here is the experiment where they now really do this NAS benchmark and they
 compare with other methods. So some of these other methods are designed to do the call weight
 sharing, which basically is a technique where you can sort of speed up the speed up the algorithm
 as compared to non weight sharing and the non weight sharing. That's one of these we have discussed
 initially. That was my initial example with the controller and so on where it takes super long.
 So here you see the method and how long each method takes. Now the best ones, as you can see
 already, the best ones here, or these, these methods right here are the best ones. They score
 somewhat like a 93.9 or so on C for 10, whereas these weight sharing ones, they don't perform too
 well, except this one seems to perform quite well. And in this hours case, they perform worse than
 that, but they still perform better than a lot of the weight sharing ones. So what their point is
 basically is that they get a pretty good score, which is a 91.5 on C for 10, which is, you know,
 it's at least not degenerate. It's a, it's a good accuracy. They score that with simply evaluating
 10 architectures, right? And as n goes up, as they evaluate more and more architectures, they do,
 they do get better, but not much. So they have a discussion here. I'm having trouble moving this.
 All right, so we'll sort of go through the discussion. We report results, yada, yada, yada,
 yada, yada. As the setup, the non weight sharing methods are given a time budget of 12,000 seconds
 for our method and the non weight sharing methods are averaged. Accuracies are averaged over 500
 runs for weight sharing methods. Accuracies are reported over three runs with the exception of
 G Das. Our method is able to outperform all the weight sharing methods while requiring a fraction
 of the search time. And that you may see at the table. This is the real, I mean, this is the real
 deal here. They only use here 1.7 seconds compared to the 12,000 seconds of the other methods. And
 you reach almost the same accuracy. Now to be said, 2% in this particular regime on C410 is still a
 sizable difference. And that's the same benchmark, right? With the same sort of the same training
 schedule and so on. So there's not too much room to tune here. You simply have to find a better
 architecture. So these things are still sizably ahead of this. And what it appears to me that
 these methods here that don't perform well, they're simply crap. It seems they're simply,
 I don't know, but they might be trying out something or, you know, doing something
 researchy or whatnot. But it seems like if you're well able to weed out the bad architectures,
 you might be getting to a score like this. And then if you are actually performing a search to
 find the best one, then you might be getting to somewhere like this. And you can see this here
 throughout. So in C4100, they achieve a better score than these things, but a worse score than
 the non-weight sharing method. And in ImageNet, the difference is even larger. So again, what I
 can see here is that theirs is a good method to maybe get you, let's say, 90% of the way you want
 to go. And what's interesting is that here they say, we also show the effect of sample size. We
 show the accuracy of the networks chosen by our method for each n. So that's the sample size.
 We list the optimal accuracy for sample sizes 10 and 100 and random selection over the whole benchmark.
 So in this case, they have the optimal one, which I guess they just draw 10 samples and then take
 the best one. So they train all of them and then take the best one. And you can see that
 already gets you to the 93. And whereas in their case, sometimes when they add more, they get worse.
 So here they get better, but then they get worse again. So they comment on this right here. We
 observe that the sample size does not have a large effect on the accuracy of our method. But note
 that as sample size increases, our method suffers from a small amount of noise, increasing the gap
 between our score and the optimal result. And of course, the key practical benefit is execution
 time. So again, they are massively faster than the other methods. But to me, it seems you could
 just think of combining these methods, right? You combine this with this in that what you want to do
 is actually actively search for the best ones. But by doing so, you could, if you could pretty
 quickly weed out the bad ones using this method down here, you might already have like a big speed
 up. Because again, with comparison to this random ones, what appears to happen is that they get good
 at finding, you know, your 90% architecture, but then they fail to differentiate the top
 performance performers from each other, where you'd really have to train the network to find out
 what's, you know, which one's better. So yeah, here they say they visualize the trade off between
 search time and accuracy for C410 for different NAS algorithms on the NAS benchmark. By removing
 the need for training, our method is able to find accurate networks in seconds instead of hours.
 And here you can see the accuracy and here you can see the time and all the good ones are either
 way over here or here. And theirs is almost at zero while being quite close to the accuracy of
 the other ones. All right, yeah, that was that was this paper. Again, I think this is pretty
 valuable if you are especially if you're in a new domain, where you might not know what kind of
 network to build, you might just be able to write a little script that generates networks, run it
 through this algorithm, and at least you get an idea of which ones are certainly not worth
 considering. And then you can simply select one of the other ones. It doesn't, you know, often it
 doesn't need to be the best ones. And you can then tweak it a little bit manually, the ones you found,
 maybe you see some regularity. And yeah, that was my two cents on this paper. I hope you liked it.
 If you did, consider sharing it out and telling your friends about it and subscribing, liking,
 and leave a comment if you agree or disagree. That was it. Bye bye.