Deep Networks Are Kernel Machines (Paper Explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper what is deep learning deep neural networks neural networks gradient descent kernel machines kernel trick svm support vector machine sgd stochastic gradient descent machine learning theory pedro domingos linear regression nearest neighbor representations data representations representation learning proof math proof learning theory representer theorem
#deeplearning #kernels #neuralnetworks

Full Title: Every Model Learned by Gradient Descent Is Approximately a Kernel Machine

Deep Neural Networks are often said to discover useful representations of the data. However, this paper challenges this prevailing view and suggest that rather than representing the data, deep neural networks store superpositions of the training data in their weights and act as kernel machines at inference time. This is a theoretical paper with a main theorem and an understandable proof and the result leads to many interesting implications for the field.

OUTLINE:
0:00 - Intro & Outline
4:50 - What is a Kernel Machine?
10:25 - Kernel Machines vs Gradient Descent
12:40 - Tangent Kernels
22:45 - Path Kernels
25:00 - Main Theorem
28:50 - Proof of the Main Theorem
39:10 - Implications & My Comments

Paper: https://arxiv.org/abs/2012.00152
Street Talk about Kernels: https://youtu.be/y_RjsDHl5Y4

ERRATA: I simplify a bit too much when I pit kernel methods against gradient descent. Of course, you can even learn kernel machines using GD, they're not mutually exclusive. And it's also not true that you "don't need a model" in kernel machines, as it usually still contains learned parameters.

Abstract:
Deep learning's successes are often attributed to its ability to automatically discover new representations of the data, rather than relying on handcrafted features like other learning methods. We show, however, that deep networks learned by the standard gradient descent algorithm are in fact mathematically approximately equivalent to kernel machines, a learning method that simply memorizes the data and uses it directly for prediction via a similarity function (the kernel). This greatly enhances the interpretability of deep network weights, by elucidating that they are effectively a superposition of the training examples. The network architecture incorporates knowledge of the target function into the kernel. This improved understanding should lead to better learning algorithms.

Authors: Pedro Domingos

Links:
TabNine Code Completion (Referral): http://bit.ly/tabnine-yannick
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/
BiliBili: https://space.bilibili.com/1824646584

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: 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 Every Model Learned by Gradient Descent is Approximately a Kernel Machine by Pedro Domingos. This paper on a high level establishes a theoretical connection between gradient descent learned models such as deep neural networks and kernel machines as you might know them from topics such as support vector machines. The paper puts its own finding as meaning that deep neural networks essentially store that training data in their parameters as a superposition. And when a new data point comes in, what it does is it sort of compares the data point to the stored training data and then decides with relation to that data what the output should be, which is of course exactly what a kernel machine does. So it is a theoretical paper and we're going to go over it. I'm not an entire expert on these things, but the main theorem is fairly easy to grasp and the proof behind it is also fairly easy. So I thought it'd be a good paper to look over. Further Pedro is coming to our Machine Learning Street Talk podcast in the future and I wanted to get familiar with his work. So you know, if you like content like this too, let me know. Let me know if you understood it or not. Or if I just made it worse. Yeah. Let's dive into the abstract. The abstract is actually a pretty good summarization of what the conclusions of the paper are. It says, deep learning successes are often attributed to its ability to automatically discover new representations in the data rather than relying on handcrafted features like other learning methods. And as you might know, this is the success story of deep learning. Before deep learning, we had to do a lot of hand crafting of features where expert knowledge went into problems and then we would simply aggregate the handcrafted features with some sort of linear classifier or, you know, in some cases, a kernel classifier. Though the hand crafting of features would also go into kernel design. Deep neural networks are different because we just feed in the training data as is. And the deep neural network will automatically discover the features that are important. At least that's the prevailing notion of what's happening. This paper challenges this view. They say we show, however, that deep networks learned by the standard gradient descent algorithm are in fact mathematically approximately equivalent to kernel machines, a learning method that simply memorizes the data and uses it directly for prediction via a similarity function, the kernel. So that's the main thesis of the paper. They show that it is equivalent to a kernel machine. If you don't know anything about kernels, don't worry. There is a good machine learning street talk episode with Alex Stanlick, where I get to ask all the dumb questions about kernels. So you don't have to ask them. So if you're interested in that, check that out as well. That's on the machine learning street talk podcast. They say this greatly enhances the interpretability of deep network weights by elucidating that they are effectively a superposition of the training examples. So saying again that the deep neural networks essentially store the training data in their weights and then use that to compare new data points to. Now, the conclusion of this paper is interesting. I don't fully agree. I don't agree with the framing here that it's sort of replacing this notion. I think this gives rise to sort of a dual view of the problem. It is a way that you can also look at these deep neural networks. I don't think it kind of changes. Like it can both be true that they do discover good representations and also are a superposition of the training data. I think it's simply a different way of looking at the problem. However, as I said, I'm not a super duper expert on this. And they allude to the fact here that this improved understanding should lead to better learning algorithms. And of course, even though this paper here is has no impact for practitioners down the road, this could actually have some of an impact. So what is a kernel machine? A kernel machine is this thing right here. So in machine learning, we always want to we have some x and this is our input data and we want to get some y. Now, for the purposes of this paper, think of y being just a number. So think of linear regression, okay, not linear, but just regression, where y is a number, x is a data point, and we want to function f that assigns each data point a number. And then that number is going into a loss function. So there is going to be a loss function that compares that number to the number that we have in the training data set our true label y star, okay, so we have training data x i, this gives so the neural network gives an output y, we compare that to the true label in the loss function. Now, a kernel machine is a particular way of how this f here is built. And usually, if you think of this as a neural network, you simply say, oh, x goes into layer, layer, layer, layer, and at the end, you get y, okay, a kernel machine is different, a kernel machine actually builds a database of all the training examples. So what it would do is it takes your training data set, and it would sort of build a list of all the training data points in here, I'm super oversimplifying this, but it will build a list of all the training data right here. And now when you want to know about a new data point, say you want to classify this x right here, what it will do is it will go to its database, and it will compare x to each of those training data points to each. And from each of those training data points, you get a response of how similar is x to that training data point. So for for the first training data point, you would get a score of how similar that is. And that score is computed by this kernel function, so x one, and kernel of x with x two, you get kernel of x with x three. So for each data point, you want to know how similar is the data point that you wonder about to the data points that you've already seen. If we look at this in kind of a schematic, so let's say this is our data space, and you have kind of a data point here and one here and one here and one here in the training data set. And you want to know how should I classify this red data point right here, your kernel will tell you and it looks easy if it's on the plane, but it's not easy at all in high dimensions with complicated data like images or, or structured data. It's not as easy as simply taking the distance though here it is. So here a good kernel function would simply be the Euclidean distance to these data points. And this says something like the kernel function would tell you that these two data points right here are very similar to the data point we care about. While these two data points right here are not that similar. So when you classify the data point, you consider all the data in your training data set, at least in the ground case. So here is your training data set. And your kernel will tell you how similar each one is. Okay, that's the kernel. And then you take that similarity and you aggregate the labels of the training data points since you know and the labels they are in here. So y star, it says AI here, but why I star so the true label is usually what gives rise to this a doesn't need to be the true label. But in the simplest case, you will simply aggregate the labels of these data points in in proportion to how close they are, it's it's a bit of a nearest neighbor classifier. Okay. So that's a kernel machine. The important thing is that there is this kernel, this is a function that tells you how close any two data points are. And there is this sum right here. So that means that the your prediction y is going to be can be a nonlinear function of the sum, but it's going to contain a sum over the training data. Okay, and each training data point is measured in its similarity through the kernel function. And then the labels of the training data points are aggregated. That's a kernel machine. So you don't you don't need, you know, any model for this, right? The learned parameters here are often the the A's and the B right here, the offset. However, the kernel can also be learned, but very often, the kernel is also fixed. And you can see immediately that choosing the kernel is the name of the game in kernel machines. And before deep learning, lots and lots of an expert engineering has gone into building kernels to measure distances between data points using kind of expert knowledge from a field. It's probably still advisable today. Some people claim we rely too much on neural networks to do this for us. But you know, neural networks have been pretty, pretty good. So what's gradient descent, you might know gradient descent, gradient descent means that we do have a loss function right here. And it is differentiable. So what we can do is we can simply calculate the gradient with respect to the loss function. And then change the parameters that we're learning into the direction of that gradient. And we arrive at a new at a new weights, and we repeat the process. So if you think of linear regression, for example, you shouldn't simply have x here and y here. And you might have sort of three data points like this. What would a kernel machine do? A kernel machine would do the following if you're trying to classify a new data point like this one right here, the kernel machine will go look which of the data points that you already have are close. This one on the right here is pretty close. This one is kind of close. This one is very far apart. And then it would sort of aggregate the labels and it would say, well, since you are very close, I'm just kind of going to copy your label. And maybe I'll adjust it a bit into the direction of view who are also pretty close to a bit down. So I might classify myself as this. What would a linear regression learned by gradient descent do? On the other hand, you have the same data points, it would start out with a line like like this, any, you know, any any old line will do randomly initialized. And then it would calculate, sorry, it would calculate the gradient. And important in this paper, we're always talking about full batch gradient. So no stochastic gradient descent, which always means that we always in every step, consider the entire data set. So here we ask this point. And this point says, well, maybe line you should you should come down a bit to the right. And then this data point also says, well, maybe you should come a bit to the right. And this data point says, well, maybe you should come a lot to the right. So that line is going to shift to the right. And ever so slightly, it will arrive at sort of this optimum right here. Whereas the data point on the bottom here says, well, I'm pretty fine, then this data point says, you should probably go up a bit. And this one says, you'd probably go down a bit. So the line just stays at the same place. That's gradient descent. Now we're going to connect the two. And in order to connect the two, we have to introduce these path kernels right here. These are very connected to neural tangent kernels, which I'm an absolute noob at. But if you know that you already sort of know what's coming. So we need this quantity right here, which is the path kernel, as we said, in kernel machines, choosing the kernel is the name of the game. And the goal of this paper is to show us that if you choose your kernel like this, then a neural network or any model learned by gradient descent is a kernel machine with this particular kernel. Okay. So first of all, we need to understand what that kernel is. So what does a kernel do a kernel measures how close two different data points are. Now, you can measure this in many ways, right. But here, we need a very particular way of measuring how close two data points are. So what might be a bit special to you is again, consider a model that we learn using gradient descent, such as this linear regression example, we start out with a line that's too steep, and we slowly come down right to the line that is the optimum line. So what we've done is we've started with w zero, and we slowly ended up with w and they call it w final right here. Okay, so during that time, the weights took a path if we draw the weights over time, right, first they were too high, and then they came down. And now they are still positive, but they sort of converge at this level. Okay, that here amounts to a path. So the weights took a path during learning, the interesting thing in this paper is what we need to do is we need to consider the entire path from beginning to end. So usually models only store, you know, the converged optimum, but here, we assume, right, we assume we have a model that's been trained by gradient descent. Okay. And that model has a history, the history of gradient descent, where we start out at w zero, and we go a path, which is this curve you see right here to w final. So imagine that during gradient descent, we have stored along the way we've stored every single step of gradient descent. Now in this paper, we consider infinitely small steps, but just imagine, you know, at every step, we actually stored the model during training. Okay. By the way, this is not a training procedure that we're describing here, right? We assume that we've already trained the model using gradient descent. And now we have the trained model, and we want to see how similar our two data points. Okay, so okay, so let's say we have a we have a data point, how do we classify it for that you need to consider these quantities right here, which is the gradient of the function of y with respect to w. So remember before we said x to y to the loss. Okay, that's our thing. Now usually, usually, x to y is f our neural network, and that has parameters w. So usually, what we do is we consider the gradient of the loss function with respect to the weights. Okay, that's what you usually do in gradient descent. So it connects, it connects the weights right here with the loss function right here, essentially, it says, how do I need to change the weights to make the loss change a certain way? Okay. Now this quantity here is different. It only connects the weights, it connects the weights to the w right here. So if you see this thing, w of x, this is the same as f of x, right? So y is a function of x. So this quantity essentially says, if I change my weights, how will the output of the neural network change? Not the loss, how will the output change? It's kind of a sensitivity measure. Okay. So imagine you have a neural network, right with with a bunch of weights, a bunch of layers, how and you have two data points, x one and x two, these are training data points, and you have your new data point x. Now you want to know is it similar to x one or x two? So what would you do in this particular case? What you do is you forward propagate both of these data points, not to the loss but to their outputs. Okay, so if, if your neural network, let's consider this as our linear regression example, and let's consider not the not the beginning, not the end, but let's consider a model sort of this model right here. Okay. And you have two data points, x one, and x two. And we want to look at not the loss, right? We don't, we want to look at if we use the model to output the data points as so. What's the gradient? How, how if we change the weights, either in this or in this direction, how does the output change? Now, for this data point right here, you can see if we change the line a little bit, the y value isn't going to shift as much because we're very close to the origin. However, for the data point up here, the y value is going to shift more for a given amount of shifting the line. So the this is going to result in a number right? x one will have a gradient, I don't know, like three, and x two is gradient of so it's gradient of y with respect to w will be something like nine. Okay. And now, the important part is we input x, so we input x, and we also get a y from the model. No, we never consider the labels here. So we have y right here, x right here. We also use it to predict. And now we ask, if we now consider the same thing, we now consider gradient of the output of this particular x with respect to the weights, what is it? And here you can see the point I've drawn also is fairly a lot away from the origin. Therefore, it's it its output will shift a lot if the weights shift. So maybe that's eight. So now you can see that by this number, we can now classify the similarity, you can see eight and nine are much closer than three and eight. Okay, so two data points in this view are similar. If if changing the weights of the neural network changes their outputs in a similar way, right? So the outputs here can actually be vectors and so on, if you want. And what you what you do is you consider the inner product between these gradients. No, sorry, it's not that the output can be vectors, actually, the weights are vectors, right? So you want to know how you need to change the weight to affect a particular change in the in the output. Yes, I was I formulated it the wrong way. And in linear regression, it ends up being the same thing because you only have one parameter. But usually, you have lots of parameters, that means you get a vector as this gradient. And you consider the inner product of these vectors as your similarity. So what does it mean when two vectors are similar of these gradients? It means that if I for data point x, if I change my weights in a certain way, how will that affect why or in other in other words, if I want my y to go up, what way do I need to change the weights? Now it's correct. So for this data point, if I want the the y value to go up, how do I need to change my weights to achieve this, right? Over here, it's the same, right? If I want my y to go up, it's just the inverse, like I need to change the weights. If I want to go to go up by one unit, I need to change the weights by one ninth. And here by one eighth, I don't need to change the weights much to make it go wild because it's so far away from the origin. However, here I need to change my weights a lot more like by one third in order to make the output move. All right. So if for two data points, they need similar changes to the weights in order to affect the same change in output, they are considered similar, okay, they they have a similar effect on the neural network dynamics. And here you can see this in action. So for a given weight configuration, we input all the three data points into the neural network, we evaluate these gradients of the output, not of the loss of the output with respect to the weights, and we compare that gradient of the three data points, it the new data point will be closer to one of them than to the other. And that's how we evaluate similarity. Now, what does this path have to do with this? So as I said here, we've simply chosen a model, right, we can, we don't have to do this for the final model, we can do this for any model. And in fact, what we're going to do is if we have a new data point, so remember that our model evolved from this down here to this, if we have a new data point, we're going to rewind time and start out at the beginning with the first model, do this measurement, like compare our data point to all the other data points for this model, then we're going to advance one step, and we're going to do it again and advance one step and we're going to do it again. And we're going to consider the similarity scores over as an average over that path. So that means, in order to classify a data point in this view, as I said, this is not a practical algorithm. In order to classify a data point, we're going to retrace the path of weights that the model took during gradient descent when it was learned, we're going to retrace that along the path. And for each step in the path, we're going to compare our data points effect on the neural network. So the neural networks sensitivity to our data point. And we're going to compare that with the neural networks sensitivity to all the data points in our training example. And then we're going to classify our data point by whichever data points in the training example had a similar effect on the neural network over the course of training. Okay, so we're not going to train the network more or anything, we're simply going to replay the path we took during gradient descent. And by looking at how the data points affect the network during that path in terms of their gradients, like how much they pull on the network, even though we're not going to do the steps. By those polls, we classify how if two data points are similar or not. And that is called this path kernel. So we have the most important quantity we have already. If you made it through here, good job. So here we have the tangent kernel associated with function f. So f is going to be our neural network, w our weights, x is a data point, and parameter vector v is going to be the inner product of these two gradients. So two data points are close in the tangent kernel, if the gradients of those data points align, so if the inner product is high, okay, and that's the tangent kernel. And the path kernel now is simply the tangent kernel integrated over the path over any path. So this is not even gradient descent yet, we can do any curve, but the curve we're going to end up looking is the curve that gradient descent took during training of the model. So I'm going to look across the whole path of gradient descent, we're simply going to integrate these tangent kernels, which gives us sort of an average, an average tangent kernel over the course of training. Now theorem one is the main theorem, it says suppose the model y equals f w of x, and f is a differentiable function of w, that's a neural network fulfills all of that, is learned from a training set, x i with y star i, right, so we have m training data points by gradient descent, so we learn it by full batch gradient descent. So each and every step, we're going to consider the whole training data set, we're going to consider the loss with respect as an average over the whole training data set of x i, so x i will give rise to y i through the neural network, and that's going to be compared with y i star, and that's going to be our loss, we're going to differentiate the loss with it says right here with a differentiable loss function, which can be in regression, it can be the square loss, right, so the loss function is a sum here as you can see, so this is what the neural network predicts, and this is what you would like to have, and the loss function simply compares the two, and the learning rate epsilon, then, then, in the limit of infinitely small steps, and that's something you do in order to be able to do continuous analysis. So it just think if we if you take small enough steps, then y equals this thing right here, which is exactly the form of a kernel machine. Okay, notice that this and this are now connected. Okay, so that thing here, this is f w of x, okay, so that the theorem essentially says that the the neural network can also be represented as a kernel machine, where k is the path kernel associated with f w of x, and the path taken by the parameters during gradient descent. ai is the average loss derivative along the path weighed by the corresponding tangent kernel, and b is the initial model. Okay, so the important thing here is that this k is going to be this path kernel we just considered, and the path that we're looking at is the path taken by the parameters during gradient descent, we need all of those things. Okay, so we're going to go into the proof. And the proof, as I said, it's fairly simple, it's fairly straightforward. And it gives sort of an idea of how does connection come to be. So first of all, we're going to consider what does gradient descent do, right? If we rewrite the equation of gradient descent, we can see we can come to this. So this is one step of gradient descent. And we're simply considering the difference between two steps. Now the difference is exactly going to be the gradient, because that's going to be the steps. And here is the step size. Now as we let the step size go to infinitely small, this of course becomes a continuous function. So this is where the gradient descent comes into play. We're saying that the way our weights change over time, right, this is the way our weights change over time is always in the direction of the negative gradient of the loss function. Right, that's, that's the continuous form of gradient descent. Now, it says this is known as gradient flow. Now, we're going to consider a different quantity, namely, how do the neural network outputs change over time? So as we already said, right? No, like, we didn't already say this. How do the neural network outputs change over time? Well, I can simply I can simply use the chain rule here to expand this into the following quantity. So how do the neural network outputs change over time? That's the derivative of the output with respect to each of the weights. So this is this is over number of parameters. I'm going to sum, sorry, over each of the parameters. And then how do these weights change over time? Okay, so how the neural network output changes over time is defined by how the weights change over time, and how the output reacts to those weight changes over time. And it's a it's a sum with with in accordance to the rules of total differentiation. So now, we've already seen the quantity on the right here, right? How do the weights change over time? Well, they change according to the loss gradient. Okay, so we're simply going to replace this here by what we established before. So each weight changes according to its derivative from sorry, according to the loss derivative with respect to that weight. This is where gradient descent enters the proof. Now, what we can do is we can apply the additivity of the loss. So we know that the loss is always an addition or a mean or a sum over the training data. So now we're going to bring that in. Okay, so the loss here, this one, we're going to split that up into its components. Since the loss is a sum over the individual losses, that means the gradient of the loss or the derivative is also a sum of derivatives. And again, the chain rule, we know that x goes to by means of w goes to y goes to L, you can if you have a gradient of L with respect to W, you can decompose that as the gradient of L with respect to y, and then the gradient of y with respect to W, you young kids know this as backpropagation. So that's exactly what we're going to do right here. Split that up with the chain rule. So now we have two quantities. The first quantity is how does the loss change with respect to the neural networks output, right? And that's pretty simple. Like this is for linear regression. This is when where the loss is the squared norm difference or the squared than this the norm of the difference of two wise. So the derivative is simply going to be something like the true label minus whatever the neural network outputs. And the other quantity right here is how does the output of the neural network change with respect to the weights. So if I change the weights of the neural network, right? x, if I change the weights a little bit, how does the output change over here? This is a quantity we've already seen. I hope I hope so. Right? Okay, meanwhile, we've we've pulled out the other quantity right here. And you might recognize it as the same quantity. Note that this here this y i means that it's a particular training data point. Whereas this y is the actual point we are trying to predict for a given input. Okay, so now we simply rearrange a bunch of terms. And look at that. Look at what comes out. So over here, we rearrange this, what you see is some over the number of parameters. Again, that's the number of parameters. And here, why won't you see this here is, if I incorporate the sum, this is the gradient with respect to the weights of f of x. And this here is the gradient with respect to the weights of f of x i, right, because it's the if training data point, and they are multiplied, right, the sum and the product means that's a dot product. So this is exactly this path is kernel, the tangent kernel, this is the tangent kernel, with respect to a particular set of weights w, okay, at a particular time in the algorithm. So at some point in this path, that's we choose a bunch of W's. And that's what results, right, this other quantity right here, as we said, this is the relatively easy quantity that simply defines how a loss changes whenever the neural network outputs change. And this is also now with respect to a particular data point. So we're going to rewrite a bit right here. So this L prime is going to be defined as that it's just a bit of a rewrite. And here, this is this tangent kernel. And now what we're going to do is we're simply going to aggregate all of this. So since this says, how does y change over time during the course, what we're going to do is simply we're going to start off somewhere, go along the path, and we're going to aggregate all of the y changes during this. So in this particular case, you know, y goes up, y goes up, y goes down, y goes down, if we aggregate all of the changes in y over the course of the of this path, we're going to end up with the final y, right. So we're simply going to aggregate all the changes in y over this course, which means we're, if we start out with a particular y, going to end up at the end. So this, it's a bit special. But this essentially means that if we look at the neural network at the beginning of training, right, we simply, if we have a new data point, we're simply going to input it into the W zero neural network, right, and that gives us y zero, that is whatever the neural network would have predicted had we not trained it. And then we're going to trace the changes in y, these, the dy dt, we're going to trace them over the course of the training that gradient descent has done, we're going to accumulate all of the changes in y that would have resulted had we input our data point at each time. And what we're going to end up with is the final y, it's a very complicated way of, of, because we could simply input the data point into the final model, right, that that will be so much easier, but we're going to input it into the start model, then we're going to consider how the output changes in each time step. And that's how we're going to end up at the final y. So yeah, so as you can see, now, this is already in the form of kind of a kernel machine, they're going to make it a little bit more like the classic form by actually averaging over this path kernel, such that you end up with this form right here. But essentially, what you can see is that this thing here measures the distance between data points by means of retracing the steps along gradient descent. And then this thing here is the measures the loss derivative with respect to these data points. Now, in order to actually bring this into a kernel form, what, yeah, as I said, they normalize by this thing, but it's essentially the same. So I hope you can see that the connection right here, as I said, you always want to you have a one way of measuring distance, and then you want to aggregate the values. So you measure distance by how sensitive other data points are by how sensitive other data points make the network. And you see which of the other data points makes the network sensitive in a similar way to yours over the course of the gradient descent time. And once you have the similarities, you simply aggregate their sort of opinion on the output with respect with weighted by how similar they affect the network to your data point. All right. That's how you come to conclude this proof. I have a lot of remarks right here. So they say this for example, this differs from a typical kernel machines in that the AIs and Bs depend on X, which is something that's not the AIs and Bs are usually kind of learned, but here they are actually functions of X, which is a difference to classic kernel machines. Essentially, you can't like in order to make this a kernel machine, right, you have to have the train neural network already. So it's not like this is a new training algorithm. It simply casts these models in the way of a kernel machine. And it's, in my mind, it's almost like it's a super general statement. It also connects it to boosting right here. I don't even know where but down here in the discussion, it connects it to boosting. And it just seems like at some point, yeah, you can just connect all the learning algorithms to each other, because all the learning algorithms will somehow incorporate the training data into their weights, like otherwise they wouldn't learn. And I feel like we're rediscovering just different methods of looking at problems. Now these different methods, the different way of looking at a problem can give rise to new and better algorithms because we understand the problem better. But yeah, it's in some way, it's not a surprise. It's not a surprise that neural networks somehow store the training data, because of course, any learning algorithm must do so. And that's exactly what this this paper shows. And it shows what the exact kernel is you have to choose in order to make that claim solid. So that was the paper I just want to read the kind of most at some point, they say the most important point for this most significantly, however, learning path kernels machines via gradient descent, largely overcomes the scalability bottlenecks that have long limited the applicability of kernel methods to large data sets, computing and storing the gram matrix at learning time with a quadratic cost and the number of example is no longer required. So makes the claim that if you want to build a kernel machine, you might as well. I don't actually know what that means. Does it mean you might as well find the neural network that is equivalent to the kernel you want to build? It? I don't know if that just that just seems to turn out to to mean that you should build the neural network that you like. But they kind of make the point that neural networks don't discover new representations, new features, what they actually do is they discover features that the of how you compare data points in this gradient space. And they do that by means of gradient descent. And the paper states that this is, you know, this is very, very dependent on how you choose the architecture. So by choosing the architecture of the neural network, you sort of predispose the gradient descent algorithm to find certain certain features to compare data points, as opposed to other features. And the paper again makes this explicit by showing how how this comparison comes about, namely by means of the gradients with respect to the weights of the output of the neural network, which of course is, you know, entirely a function of both the architecture and the loss function and the data set. All right, so I hope you've enjoyed this. Let me know what you think and I'll see you next time. Bye bye.
 Hi there. Today we're looking at Every Model Learned by Gradient Descent is Approximately
 a Kernel Machine by Pedro Domingos. This paper on a high level establishes a theoretical
 connection between gradient descent learned models such as deep neural networks and kernel
 machines as you might know them from topics such as support vector machines. The paper
 puts its own finding as meaning that deep neural networks essentially store that training
 data in their parameters as a superposition. And when a new data point comes in, what it
 does is it sort of compares the data point to the stored training data and then decides
 with relation to that data what the output should be, which is of course exactly what
 a kernel machine does. So it is a theoretical paper and we're going to go over it. I'm
 not an entire expert on these things, but the main theorem is fairly easy to grasp and
 the proof behind it is also fairly easy. So I thought it'd be a good paper to look over.
 Further Pedro is coming to our Machine Learning Street Talk podcast in the future and I wanted
 to get familiar with his work. So you know, if you like content like this too, let me
 know. Let me know if you understood it or not. Or if I just made it worse. Yeah. Let's
 dive into the abstract. The abstract is actually a pretty good summarization of what the conclusions
 of the paper are. It says, deep learning successes are often attributed to its ability to automatically
 discover new representations in the data rather than relying on handcrafted features like
 other learning methods. And as you might know, this is the success story of deep learning.
 Before deep learning, we had to do a lot of hand crafting of features where expert knowledge
 went into problems and then we would simply aggregate the handcrafted features with some
 sort of linear classifier or, you know, in some cases, a kernel classifier. Though the
 hand crafting of features would also go into kernel design. Deep neural networks are different
 because we just feed in the training data as is. And the deep neural network will automatically
 discover the features that are important. At least that's the prevailing notion of what's
 happening. This paper challenges this view. They say we show, however, that deep networks
 learned by the standard gradient descent algorithm are in fact mathematically approximately
 equivalent to kernel machines, a learning method that simply memorizes the data and
 uses it directly for prediction via a similarity function, the kernel. So that's the main thesis
 of the paper. They show that it is equivalent to a kernel machine. If you don't know anything
 about kernels, don't worry. There is a good machine learning street talk episode with
 Alex Stanlick, where I get to ask all the dumb questions about kernels. So you don't
 have to ask them. So if you're interested in that, check that out as well. That's on
 the machine learning street talk podcast. They say this greatly enhances the interpretability
 of deep network weights by elucidating that they are effectively a superposition of the
 training examples. So saying again that the deep neural networks essentially store the
 training data in their weights and then use that to compare new data points to. Now, the
 conclusion of this paper is interesting. I don't fully agree. I don't agree with the
 framing here that it's sort of replacing this notion. I think this gives rise to sort of
 a dual view of the problem. It is a way that you can also look at these deep neural networks.
 I don't think it kind of changes. Like it can both be true that they do discover good
 representations and also are a superposition of the training data. I think it's simply
 a different way of looking at the problem. However, as I said, I'm not a super duper
 expert on this. And they allude to the fact here that this improved understanding should
 lead to better learning algorithms. And of course, even though this paper here is has
 no impact for practitioners down the road, this could actually have some of an impact.
 So what is a kernel machine? A kernel machine is this thing right here. So in machine learning,
 we always want to we have some x and this is our input data and we want to get some
 y. Now, for the purposes of this paper, think of y being just a number. So think of linear
 regression, okay, not linear, but just regression, where y is a number, x is a data point, and
 we want to function f that assigns each data point a number. And then that number is going
 into a loss function. So there is going to be a loss function that compares that number
 to the number that we have in the training data set our true label y star, okay, so we
 have training data x i, this gives so the neural network gives an output y, we compare
 that to the true label in the loss function. Now, a kernel machine is a particular way
 of how this f here is built. And usually, if you think of this as a neural network,
 you simply say, oh, x goes into layer, layer, layer, layer, and at the end, you get y, okay,
 a kernel machine is different, a kernel machine actually builds a database of all the training
 examples. So what it would do is it takes your training data set, and it would sort
 of build a list of all the training data points in here, I'm super oversimplifying this, but
 it will build a list of all the training data right here. And now when you want to know
 about a new data point, say you want to classify this x right here, what it will do is it will
 go to its database, and it will compare x to each of those training data points to each.
 And from each of those training data points, you get a response of how similar is x to
 that training data point. So for for the first training data point, you would get a score
 of how similar that is. And that score is computed by this kernel function, so x one,
 and kernel of x with x two, you get kernel of x with x three. So for each data point,
 you want to know how similar is the data point that you wonder about to the data points that
 you've already seen. If we look at this in kind of a schematic, so let's say this is
 our data space, and you have kind of a data point here and one here and one here and one
 here in the training data set. And you want to know how should I classify this red data
 point right here, your kernel will tell you and it looks easy if it's on the plane, but
 it's not easy at all in high dimensions with complicated data like images or, or structured
 data. It's not as easy as simply taking the distance though here it is. So here a good
 kernel function would simply be the Euclidean distance to these data points. And this says
 something like the kernel function would tell you that these two data points right here
 are very similar to the data point we care about. While these two data points right here
 are not that similar. So when you classify the data point, you consider all the data
 in your training data set, at least in the ground case. So here is your training data
 set. And your kernel will tell you how similar each one is. Okay, that's the kernel. And
 then you take that similarity and you aggregate the labels of the training data points since
 you know and the labels they are in here. So y star, it says AI here, but why I star
 so the true label is usually what gives rise to this a doesn't need to be the true label.
 But in the simplest case, you will simply aggregate the labels of these data points
 in in proportion to how close they are, it's it's a bit of a nearest neighbor classifier.
 Okay. So that's a kernel machine. The important thing is that there is this kernel, this is
 a function that tells you how close any two data points are. And there is this sum right
 here. So that means that the your prediction y is going to be can be a nonlinear function
 of the sum, but it's going to contain a sum over the training data. Okay, and each training
 data point is measured in its similarity through the kernel function. And then the labels of
 the training data points are aggregated. That's a kernel machine. So you don't you don't need,
 you know, any model for this, right? The learned parameters here are often the the A's and
 the B right here, the offset. However, the kernel can also be learned, but very often,
 the kernel is also fixed. And you can see immediately that choosing the kernel is the
 name of the game in kernel machines. And before deep learning, lots and lots of an expert
 engineering has gone into building kernels to measure distances between data points using
 kind of expert knowledge from a field. It's probably still advisable today. Some people
 claim we rely too much on neural networks to do this for us. But you know, neural networks
 have been pretty, pretty good. So what's gradient descent, you might know gradient descent,
 gradient descent means that we do have a loss function right here. And it is differentiable.
 So what we can do is we can simply calculate the gradient with respect to the loss function.
 And then change the parameters that we're learning into the direction of that gradient.
 And we arrive at a new at a new weights, and we repeat the process. So if you think of
 linear regression, for example, you shouldn't simply have x here and y here. And you might
 have sort of three data points like this. What would a kernel machine do? A kernel machine
 would do the following if you're trying to classify a new data point like this one right
 here, the kernel machine will go look which of the data points that you already have are
 close. This one on the right here is pretty close. This one is kind of close. This one
 is very far apart. And then it would sort of aggregate the labels and it would say,
 well, since you are very close, I'm just kind of going to copy your label. And maybe I'll
 adjust it a bit into the direction of view who are also pretty close to a bit down. So
 I might classify myself as this. What would a linear regression learned by gradient descent
 do? On the other hand, you have the same data points, it would start out with a line like
 like this, any, you know, any any old line will do randomly initialized. And then it
 would calculate, sorry, it would calculate the gradient. And important in this paper,
 we're always talking about full batch gradient. So no stochastic gradient descent, which always
 means that we always in every step, consider the entire data set. So here we ask this point.
 And this point says, well, maybe line you should you should come down a bit to the right.
 And then this data point also says, well, maybe you should come a bit to the right.
 And this data point says, well, maybe you should come a lot to the right. So that line
 is going to shift to the right. And ever so slightly, it will arrive at sort of this optimum
 right here. Whereas the data point on the bottom here says, well, I'm pretty fine, then
 this data point says, you should probably go up a bit. And this one says, you'd probably
 go down a bit. So the line just stays at the same place. That's gradient descent. Now we're
 going to connect the two. And in order to connect the two, we have to introduce these
 path kernels right here. These are very connected to neural tangent kernels, which I'm an absolute
 noob at. But if you know that you already sort of know what's coming. So we need this
 quantity right here, which is the path kernel, as we said, in kernel machines, choosing the
 kernel is the name of the game. And the goal of this paper is to show us that if you choose
 your kernel like this, then a neural network or any model learned by gradient descent is
 a kernel machine with this particular kernel. Okay. So first of all, we need to understand
 what that kernel is. So what does a kernel do a kernel measures how close two different
 data points are. Now, you can measure this in many ways, right. But here, we need a very
 particular way of measuring how close two data points are. So what might be a bit special
 to you is again, consider a model that we learn using gradient descent, such as this
 linear regression example, we start out with a line that's too steep, and we slowly come
 down right to the line that is the optimum line. So what we've done is we've started
 with w zero, and we slowly ended up with w and they call it w final right here. Okay,
 so during that time, the weights took a path if we draw the weights over time, right, first
 they were too high, and then they came down. And now they are still positive, but they
 sort of converge at this level. Okay, that here amounts to a path. So the weights took
 a path during learning, the interesting thing in this paper is what we need to do is we
 need to consider the entire path from beginning to end. So usually models only store, you
 know, the converged optimum, but here, we assume, right, we assume we have a model that's
 been trained by gradient descent. Okay. And that model has a history, the history of gradient
 descent, where we start out at w zero, and we go a path, which is this curve you see
 right here to w final. So imagine that during gradient descent, we have stored along the
 way we've stored every single step of gradient descent. Now in this paper, we consider infinitely
 small steps, but just imagine, you know, at every step, we actually stored the model during
 training. Okay. By the way, this is not a training procedure that we're describing here,
 right? We assume that we've already trained the model using gradient descent. And now
 we have the trained model, and we want to see how similar our two data points. Okay,
 so okay, so let's say we have a we have a data point, how do we classify it for that
 you need to consider these quantities right here, which is the gradient of the function
 of y with respect to w. So remember before we said x to y to the loss. Okay, that's our
 thing. Now usually, usually, x to y is f our neural network, and that has parameters w.
 So usually, what we do is we consider the gradient of the loss function with respect
 to the weights. Okay, that's what you usually do in gradient descent. So it connects, it
 connects the weights right here with the loss function right here, essentially, it says,
 how do I need to change the weights to make the loss change a certain way? Okay. Now this
 quantity here is different. It only connects the weights, it connects the weights to the
 w right here. So if you see this thing, w of x, this is the same as f of x, right? So
 y is a function of x. So this quantity essentially says, if I change my weights, how will the
 output of the neural network change? Not the loss, how will the output change? It's kind
 of a sensitivity measure. Okay. So imagine you have a neural network, right with with
 a bunch of weights, a bunch of layers, how and you have two data points, x one and x
 two, these are training data points, and you have your new data point x. Now you want to
 know is it similar to x one or x two? So what would you do in this particular case? What
 you do is you forward propagate both of these data points, not to the loss but to their
 outputs. Okay, so if, if your neural network, let's consider this as our linear regression
 example, and let's consider not the not the beginning, not the end, but let's consider
 a model sort of this model right here. Okay. And you have two data points, x one, and x
 two. And we want to look at not the loss, right? We don't, we want to look at if we
 use the model to output the data points as so. What's the gradient? How, how if we change
 the weights, either in this or in this direction, how does the output change? Now, for this
 data point right here, you can see if we change the line a little bit, the y value isn't going
 to shift as much because we're very close to the origin. However, for the data point
 up here, the y value is going to shift more for a given amount of shifting the line. So
 the this is going to result in a number right? x one will have a gradient, I don't know,
 like three, and x two is gradient of so it's gradient of y with respect to w will be something
 like nine. Okay. And now, the important part is we input x, so we input x, and we also
 get a y from the model. No, we never consider the labels here. So we have y right here,
 x right here. We also use it to predict. And now we ask, if we now consider the same thing,
 we now consider gradient of the output of this particular x with respect to the weights,
 what is it? And here you can see the point I've drawn also is fairly a lot away from
 the origin. Therefore, it's it its output will shift a lot if the weights shift. So
 maybe that's eight. So now you can see that by this number, we can now classify the similarity,
 you can see eight and nine are much closer than three and eight. Okay, so two data points
 in this view are similar. If if changing the weights of the neural network changes their
 outputs in a similar way, right? So the outputs here can actually be vectors and so on, if
 you want. And what you what you do is you consider the inner product between these gradients.
 No, sorry, it's not that the output can be vectors, actually, the weights are vectors,
 right? So you want to know how you need to change the weight to affect a particular change
 in the in the output. Yes, I was I formulated it the wrong way. And in linear regression,
 it ends up being the same thing because you only have one parameter. But usually, you
 have lots of parameters, that means you get a vector as this gradient. And you consider
 the inner product of these vectors as your similarity. So what does it mean when two
 vectors are similar of these gradients? It means that if I for data point x, if I change
 my weights in a certain way, how will that affect why or in other in other words, if
 I want my y to go up, what way do I need to change the weights? Now it's correct. So for
 this data point, if I want the the y value to go up, how do I need to change my weights
 to achieve this, right? Over here, it's the same, right? If I want my y to go up, it's
 just the inverse, like I need to change the weights. If I want to go to go up by one unit,
 I need to change the weights by one ninth. And here by one eighth, I don't need to change
 the weights much to make it go wild because it's so far away from the origin. However,
 here I need to change my weights a lot more like by one third in order to make the output
 move. All right. So if for two data points, they need similar changes to the weights in
 order to affect the same change in output, they are considered similar, okay, they they
 have a similar effect on the neural network dynamics. And here you can see this in action.
 So for a given weight configuration, we input all the three data points into the neural
 network, we evaluate these gradients of the output, not of the loss of the output with
 respect to the weights, and we compare that gradient of the three data points, it the
 new data point will be closer to one of them than to the other. And that's how we evaluate
 similarity. Now, what does this path have to do with this? So as I said here, we've
 simply chosen a model, right, we can, we don't have to do this for the final model, we can
 do this for any model. And in fact, what we're going to do is if we have a new data point,
 so remember that our model evolved from this down here to this, if we have a new data point,
 we're going to rewind time and start out at the beginning with the first model, do this
 measurement, like compare our data point to all the other data points for this model,
 then we're going to advance one step, and we're going to do it again and advance one
 step and we're going to do it again. And we're going to consider the similarity scores over
 as an average over that path. So that means, in order to classify a data point in this
 view, as I said, this is not a practical algorithm. In order to classify a data point, we're going
 to retrace the path of weights that the model took during gradient descent when it was learned,
 we're going to retrace that along the path. And for each step in the path, we're going
 to compare our data points effect on the neural network. So the neural networks sensitivity
 to our data point. And we're going to compare that with the neural networks sensitivity
 to all the data points in our training example. And then we're going to classify our data
 point by whichever data points in the training example had a similar effect on the neural
 network over the course of training. Okay, so we're not going to train the network more
 or anything, we're simply going to replay the path we took during gradient descent.
 And by looking at how the data points affect the network during that path in terms of their
 gradients, like how much they pull on the network, even though we're not going to do
 the steps. By those polls, we classify how if two data points are similar or not. And
 that is called this path kernel. So we have the most important quantity we have already.
 If you made it through here, good job. So here we have the tangent kernel associated
 with function f. So f is going to be our neural network, w our weights, x is a data point,
 and parameter vector v is going to be the inner product of these two gradients. So two
 data points are close in the tangent kernel, if the gradients of those data points align,
 so if the inner product is high, okay, and that's the tangent kernel. And the path kernel
 now is simply the tangent kernel integrated over the path over any path. So this is not
 even gradient descent yet, we can do any curve, but the curve we're going to end up looking
 is the curve that gradient descent took during training of the model. So I'm going to look
 across the whole path of gradient descent, we're simply going to integrate these tangent
 kernels, which gives us sort of an average, an average tangent kernel over the course
 of training. Now theorem one is the main theorem, it says suppose the model y equals f w of
 x, and f is a differentiable function of w, that's a neural network fulfills all of that,
 is learned from a training set, x i with y star i, right, so we have m training data
 points by gradient descent, so we learn it by full batch gradient descent. So each and
 every step, we're going to consider the whole training data set, we're going to consider
 the loss with respect as an average over the whole training data set of x i, so x i will
 give rise to y i through the neural network, and that's going to be compared with y i star,
 and that's going to be our loss, we're going to differentiate the loss with it says right
 here with a differentiable loss function, which can be in regression, it can be the
 square loss, right, so the loss function is a sum here as you can see, so this is what
 the neural network predicts, and this is what you would like to have, and the loss function
 simply compares the two, and the learning rate epsilon, then, then, in the limit of
 infinitely small steps, and that's something you do in order to be able to do continuous
 analysis. So it just think if we if you take small enough steps, then y equals this thing
 right here, which is exactly the form of a kernel machine. Okay, notice that this and
 this are now connected. Okay, so that thing here, this is f w of x, okay, so that the
 theorem essentially says that the the neural network can also be represented as a kernel
 machine, where k is the path kernel associated with f w of x, and the path taken by the
 parameters during gradient descent. ai is the average loss derivative along the path
 weighed by the corresponding tangent kernel, and b is the initial model. Okay, so the important
 thing here is that this k is going to be this path kernel we just considered, and the path
 that we're looking at is the path taken by the parameters during gradient descent, we
 need all of those things. Okay, so we're going to go into the proof. And the proof, as I
 said, it's fairly simple, it's fairly straightforward. And it gives sort of an idea of how does connection
 come to be. So first of all, we're going to consider what does gradient descent do, right?
 If we rewrite the equation of gradient descent, we can see we can come to this. So this is
 one step of gradient descent. And we're simply considering the difference between two steps.
 Now the difference is exactly going to be the gradient, because that's going to be the
 steps. And here is the step size. Now as we let the step size go to infinitely small,
 this of course becomes a continuous function. So this is where the gradient descent comes
 into play. We're saying that the way our weights change over time, right, this is the way our
 weights change over time is always in the direction of the negative gradient of the
 loss function. Right, that's, that's the continuous form of gradient descent. Now, it says this
 is known as gradient flow. Now, we're going to consider a different quantity, namely,
 how do the neural network outputs change over time? So as we already said, right? No, like,
 we didn't already say this. How do the neural network outputs change over time? Well, I
 can simply I can simply use the chain rule here to expand this into the following quantity.
 So how do the neural network outputs change over time? That's the derivative of the output
 with respect to each of the weights. So this is this is over number of parameters. I'm
 going to sum, sorry, over each of the parameters. And then how do these weights change over
 time? Okay, so how the neural network output changes over time is defined by how the weights
 change over time, and how the output reacts to those weight changes over time. And it's
 a it's a sum with with in accordance to the rules of total differentiation. So now, we've
 already seen the quantity on the right here, right? How do the weights change over time?
 Well, they change according to the loss gradient. Okay, so we're simply going to replace this
 here by what we established before. So each weight changes according to its derivative
 from sorry, according to the loss derivative with respect to that weight. This is where
 gradient descent enters the proof. Now, what we can do is we can apply the additivity of
 the loss. So we know that the loss is always an addition or a mean or a sum over the training
 data. So now we're going to bring that in. Okay, so the loss here, this one, we're going
 to split that up into its components. Since the loss is a sum over the individual losses,
 that means the gradient of the loss or the derivative is also a sum of derivatives. And
 again, the chain rule, we know that x goes to by means of w goes to y goes to L, you
 can if you have a gradient of L with respect to W, you can decompose that as the gradient
 of L with respect to y, and then the gradient of y with respect to W, you young kids know
 this as backpropagation. So that's exactly what we're going to do right here. Split that
 up with the chain rule. So now we have two quantities. The first quantity is how does
 the loss change with respect to the neural networks output, right? And that's pretty
 simple. Like this is for linear regression. This is when where the loss is the squared
 norm difference or the squared than this the norm of the difference of two wise. So the
 derivative is simply going to be something like the true label minus whatever the neural
 network outputs. And the other quantity right here is how does the output of the neural
 network change with respect to the weights. So if I change the weights of the neural network,
 right? x, if I change the weights a little bit, how does the output change over here?
 This is a quantity we've already seen. I hope I hope so. Right? Okay, meanwhile, we've we've
 pulled out the other quantity right here. And you might recognize it as the same quantity.
 Note that this here this y i means that it's a particular training data point. Whereas
 this y is the actual point we are trying to predict for a given input. Okay, so now we
 simply rearrange a bunch of terms. And look at that. Look at what comes out. So over here,
 we rearrange this, what you see is some over the number of parameters. Again, that's the
 number of parameters. And here, why won't you see this here is, if I incorporate the
 sum, this is the gradient with respect to the weights of f of x. And this here is the
 gradient with respect to the weights of f of x i, right, because it's the if training
 data point, and they are multiplied, right, the sum and the product means that's a dot
 product. So this is exactly this path is kernel, the tangent kernel, this is the tangent kernel,
 with respect to a particular set of weights w, okay, at a particular time in the algorithm.
 So at some point in this path, that's we choose a bunch of W's. And that's what results, right,
 this other quantity right here, as we said, this is the relatively easy quantity that simply
 defines how a loss changes whenever the neural network outputs change. And this is also now
 with respect to a particular data point. So we're going to rewrite a bit right here. So
 this L prime is going to be defined as that it's just a bit of a rewrite. And here, this
 is this tangent kernel. And now what we're going to do is we're simply going to aggregate
 all of this. So since this says, how does y change over time during the course, what
 we're going to do is simply we're going to start off somewhere, go along the path, and
 we're going to aggregate all of the y changes during this. So in this particular case, you
 know, y goes up, y goes up, y goes down, y goes down, if we aggregate all of the changes
 in y over the course of the of this path, we're going to end up with the final y, right. So
 we're simply going to aggregate all the changes in y over this course, which means we're, if
 we start out with a particular y, going to end up at the end. So this, it's a bit special.
 But this essentially means that if we look at the neural network at the beginning of
 training, right, we simply, if we have a new data point, we're simply going to input it
 into the W zero neural network, right, and that gives us y zero, that is whatever the
 neural network would have predicted had we not trained it. And then we're going to trace
 the changes in y, these, the dy dt, we're going to trace them over the course of the
 training that gradient descent has done, we're going to accumulate all of the changes in
 y that would have resulted had we input our data point at each time. And what we're going
 to end up with is the final y, it's a very complicated way of, of, because we could simply
 input the data point into the final model, right, that that will be so much easier, but
 we're going to input it into the start model, then we're going to consider how the output
 changes in each time step. And that's how we're going to end up at the final y. So yeah,
 so as you can see, now, this is already in the form of kind of a kernel machine, they're
 going to make it a little bit more like the classic form by actually averaging over this
 path kernel, such that you end up with this form right here. But essentially, what you
 can see is that this thing here measures the distance between data points by means of retracing
 the steps along gradient descent. And then this thing here is the measures the loss derivative
 with respect to these data points. Now, in order to actually bring this into a kernel
 form, what, yeah, as I said, they normalize by this thing, but it's essentially the same.
 So I hope you can see that the connection right here, as I said, you always want to
 you have a one way of measuring distance, and then you want to aggregate the values.
 So you measure distance by how sensitive other data points are by how sensitive other data
 points make the network. And you see which of the other data points makes the network
 sensitive in a similar way to yours over the course of the gradient descent time. And once
 you have the similarities, you simply aggregate their sort of opinion on the output with respect
 with weighted by how similar they affect the network to your data point. All right. That's
 how you come to conclude this proof. I have a lot of remarks right here. So they say this
 for example, this differs from a typical kernel machines in that the AIs and Bs depend on
 X, which is something that's not the AIs and Bs are usually kind of learned, but here they
 are actually functions of X, which is a difference to classic kernel machines. Essentially, you
 can't like in order to make this a kernel machine, right, you have to have the train
 neural network already. So it's not like this is a new training algorithm. It simply
 casts these models in the way of a kernel machine. And it's, in my mind, it's almost
 like it's a super general statement. It also connects it to boosting right here. I don't
 even know where but down here in the discussion, it connects it to boosting. And it just seems
 like at some point, yeah, you can just connect all the learning algorithms to each other,
 because all the learning algorithms will somehow incorporate the training data into their weights,
 like otherwise they wouldn't learn. And I feel like we're rediscovering just different
 methods of looking at problems. Now these different methods, the different way of looking
 at a problem can give rise to new and better algorithms because we understand the problem
 better. But yeah, it's in some way, it's not a surprise. It's not a surprise that neural
 networks somehow store the training data, because of course, any learning algorithm
 must do so. And that's exactly what this this paper shows. And it shows what the exact kernel
 is you have to choose in order to make that claim solid. So that was the paper I just
 want to read the kind of most at some point, they say the most important point for this
 most significantly, however, learning path kernels machines via gradient descent, largely
 overcomes the scalability bottlenecks that have long limited the applicability of kernel
 methods to large data sets, computing and storing the gram matrix at learning time with
 a quadratic cost and the number of example is no longer required. So makes the claim
 that if you want to build a kernel machine, you might as well. I don't actually know what
 that means. Does it mean you might as well find the neural network that is equivalent
 to the kernel you want to build? It? I don't know if that just that just seems to turn
 out to to mean that you should build the neural network that you like. But they kind of make
 the point that neural networks don't discover new representations, new features, what they
 actually do is they discover features that the of how you compare data points in this
 gradient space. And they do that by means of gradient descent. And the paper states
 that this is, you know, this is very, very dependent on how you choose the architecture.
 So by choosing the architecture of the neural network, you sort of predispose the gradient
 descent algorithm to find certain certain features to compare data points, as opposed
 to other features. And the paper again makes this explicit by showing how how this comparison
 comes about, namely by means of the gradients with respect to the weights of the output
 of the neural network, which of course is, you know, entirely a function of both the
 architecture and the loss function and the data set. All right, so I hope you've enjoyed
 this. Let me know what you think and I'll see you next time. Bye bye.