Deep Networks Are Kernel Machines

Good afternoon, everybody. Thank you all for being here. Yet another session of the NPML seminar series. So today we're very glad and honored to have Pedro Domingos with us. So Pedro actually is a son of this house. He obtained his— I don't know how to say it in English— his undergrad degree here from ISTE a long time ago. Well, not that long time ago, in 1988. And so after that, he had a brilliant career in the US. So he obtained— he got a PhD and is currently Emeritus Professor at the University of Washington, usually known as UW. And he's famously known as being the author of The Master Algorithm, which is a book for general audiences about machine learning. And he also received a lot of honors in the machine learning and AI communities, such as the CKDD Innovation Award, the IJCAI John McCarthy Award, which are very important honors in this area. He's also a fellow of the AAAS and AAII, and he received many other awards, which I won't bore you and waste this time. You probably heard this introduction many, many times. And so thank you for being with us, Pedro, and the floor is yours.

Thank you for having me. So this is going to be a one-theorem talk. I'm going to lay out the motivation and the groundwork for the theorem. I will state it. Uh, the proof is actually simple enough that I can go through it in a few slides, and then I will look at some of the implications of the theorem, which I think is what actually makes it interesting. And the, the general topic of this talk, which hopefully will be interesting to the various audiences, is to try to understand better what is going on in deep learning. Deep learning is amazingly successful, but it's really very poorly understood. I would even say shockingly so, given that we've been doing neural networks for 70 years. So, you know, I'm giving away the punchline of the talk in the title. It's called Deep Networks Are Kernel Machines. So this is what I'm going to try to convince you of. And given that it's a theorem, I think by the end of it, you should be convinced unless there's an error in the theorem, which is never impossible but unlikely. The, the main selling point of deep learning for me and for many other people has always been that they can discover new representations. They're not restricted to learning on top of handcrafted features. They do this amazing thing that they can come up with their own representations. But as, as seductive as this is and as impressive as the empirical results are that are all around us these days, This story has always felt a little patchy, right? So how exactly does this miracle happen that you do gradient descent and new representations get discovered? So the goal of this research was try to understand that a little bit better. And, and as it turns out, uh, what, as you'll see, what deep networks are doing is, um, they're actually just a kernel machine. They're memorizing examples. And then they basically apply those examples to new ones by, you know, similarity comparisons like a kernel machine does. They have a very interesting and new kind of kernel, which is what gives them their power, and that's what we will see. Also, this result does not just apply to deep networks, it applies to anything that is learned by gradient descent. So, you know, it actually has a lot of interesting implications, not just Beyond those, those for deep learning. What comes out of this, I think, has— so, you know, there's what you could say is a somewhat negative result that maybe the representation learning is not as powerful as we thought it was, but also has a very, very, I think, useful consequence, which is for interpretability. If we can now look inside that black box and see the kernel machine, And in particular, what is— what we actually have in a deep network is that the weights are a superposition of the training examples. And now this makes the network much more interpretable, much less opaque than it was before. And the opacity, lack of explainability, has always been the Achilles heel of deep networks. And I think this, this really helps with that. Another interesting insight that comes out of this is that a lot of the rhetoric, you could say, around deep learning is that it learns with very little knowledge. It's just the data. But we know that that's impossible, right? There's the no free lunch theorem. And as it turns out, what the architecture of a deep network does is incorporate knowledge. There's actually a lot of knowledge that goes into a deep network. It goes into the architecture, and we will see how. So let's get started. I'm sure you guys all know what kernel machines are, but let me just go over it quickly, mainly to lay down the notation. So, a kernel machine is, you know, I'm going to focus on classification as an illustration, but, but it's important to notice that what I'm going to say applies to all supervised learning and even unsupervised learning. So anything that you do with kernels, including kernel density estimation and whatnot, but it's, you know, a typical, shall we say, kernel machine is something that produces a prediction, predicts the class of an example. By comparing it with each of the training examples and then making a prediction that is a weighted prediction of the classes of the training examples weighted by the similarity as measured by the kernel. So more similar examples have more weight and, and, and by a weight that is also learned. So, you know, I'm going to call y the model output. It's a weighted sum where the weights are these a_i's of kernels. Kernel is k. K of x and xi. k is a function that takes 2 examples, x and xi, and returns a positive number. There's other properties that it can have that are nice, but we will not need them. And, you know, so they're not required even for a lot of the, you know, theory of kernels. b is a constant. g is an optional nonlinearity that we're not going to make use of here. So we're going to ignore it, but it's often there. Now, the, the— we've known for a long time one simple relationship between kernel machines and deep networks, which is that kernel machines are deep networks. In particular, if you look at this equation, you can see the kernels as the hidden layer and, and the g as the output layer. And in fact, there's a, there's a type of, of, of a deep network called— or not even a deep network, type of neural network called a radial basis function network that has exactly this form and used to actually be very popular and successful for a lot of applications. So we know that deep networks are— that kernel machines are deep networks. But the question is, like, what is the relationship in the other direction? And the surprise here is that, as it turns out, deep networks are also approximately kernel machines. And this at first might surprise you because you go, well, that can't be. We know there are all these theorems, you know, I'm responsible for some of them that show that you can learn some functions exponentially more compactly when you have more layers. So there has to be an exponential blowup when you try to do a deep network with a kernel machine. No? Well, here's the thing that is often overlooked is that there's a difference between being able to represent something, which is what these theorems are about, and being able to learn it. And gradient descent is a very simple, very dumb local search procedure. In fact, it's limited enough that all by itself it introduces some strong restrictions on what is going to be learned. So, in some ways, the notion that these networks can learn all these things is an optical illusion that is not materialized when you actually learn them by backprop. Maybe there are better learning methods, and that, in fact, is a a direction for future work that I will touch on at the end. So again, just very brief review of gradient descent. We have an initial weight vector, typically random, and then at each step what we do is we subtract from that weight vector the loss of the objective function, whatever it is, of the loss function or wherever it is with respect to those weights multiplied by a learning rate epsilon. And in fact, all that I'm going to do here is show that if you do this, then you get this. Okay, and, and, and we're going to see how. So the main construct that I will be using here is, is something that I call a path kernel, and the path kernel is really the core of, of this whole line of work. And, and, and if you're familiar with the neural tangent kernel, which has become very popular for analyzing deep networks, The path kernel is the integral of the neural— of the tangent kernel. I'm just going to call it the tangent kernel because it doesn't have to be neural. It applies to anything. And the path kernel is just the integral of the tangent kernel over the course of the learning, over the course of gradient descent. So, in particular, you know, I'm going to call C of T. So, T is time, right? I'm going to use, you know, continuous approximation because it makes things much cleaner and, and, and, and transparent. So C of t is the path taken by the weights during gradient descent. And so the kernel between the data points x and x prime is the integral over this contour C of t of this dot product of 2 gradients. That is the tangent kernel. So this is the gradient of the function with respect to the point x and the gradient with respect to the point x prime. So you take the gradient at both of the points with the current weights, do the dot product, integrate over time, and this is your path kernel.

Now, you know— Sorry to interrupt, just to clarify. So it should be Wt, right?

Well, yes, absolutely. And, you know, like, thanks for bringing that up. I'm using PowerPoint notation here, right? Which is, there's a lot of— so There are a lot of implicit dependencies that I took out just so there aren't too many symbols on the page. But in particular, the weights are, of course, you know, a function of time or the step that you're at. I tried to take out things that are kind of like obvious, you know, if, you know, from the background, but if you ever, you know, have doubts, just let me know and I can clarify on the spot. Yeah, thank you for that note. Here's an example that will hopefully illustrate and explain a bit what the path kernel is. So let's suppose that we have only 2 weights. So the weight space is just the plane, and we start at W0, and then the weights, you know, we do gradient descent, the weights follow some curve that ends at W final. So they go through W1, W2, et cetera. And now at each of these points, look at W1, for example, you know, the function, the current function, the current deep network, for example, has a gradient. With respect to the weights, and I can compute that gradient at any data point that I want. In particular, if I'm currently trying to classify point x, I can compute it at x. That's— those are the black arrows. And I also have the gradient at each of the data points, the training examples. So there's the gradient in red at x1, etc., etc. And now if you see here, what's happening is that over the whole trajectory of the weights the dot product of the gradient with respect to the test point and the gradient with respect to x1 is on average larger because the angle between them is smaller. Okay, and what this means by the path kernel, and as we'll see, is that this means that the— that point is going to have a greater weight in classifying the test point. So what the path kernel does is that if the trajectory of the gradient with respect to a training point is more similar to that of the test point, then other things being equal, it has a greater influence in classifying the test example. Okay, so this is conceptually what the path kernel is doing. So here's a few definitions, and then we'll state the theorem and prove it. Just, you know, to make more formal what we've already said informally. So the tangent kernel associated with the function f sub w of x and a particular parameter vector v is the following. It's the dot product of the gradient of the function at x and x prime, if the 2 points going into the gradient are x and x prime, at the point v. And then the path kernel associated with that function and with a curve c of t in parameter space is the integral of that tangent kernel over the curve. Okay, so here's the theorem. It's a bit of a mouthful, but let me go through it first just step by step so we get it down, and then we'll, you know, and then see a little bit more what it means and where it comes from. The conditions for the statement are very standard, so if you're familiar with machine learning theory, this is you know, completely straightforward. Suppose you have a model y equals f of w of x, where f is a differentiable function of the weights. That's— we had made that condition. It doesn't have to be differentiable condition— function of x, which is nice. x could be a discrete structure. It could be a graph. It could be a sentence. It could be absolutely anything that you want. And this function is going to be learned from a training set of ordered pairs, x_i and y_i*. I'm using star to denote the fact that yi star is the real class of yi— of xi, sorry. yi will be the— without the star with the prediction. And there are m of these points. And this is learned by gradient descent with a loss function that is differentiable, as, you know, they always are, and additive, again, as they always are. The loss function is L, and it's a sum of losses over the individual examples where each loss compares the yi with the yi star. and penalizes the difference in some way. And, and we have a learning rate for gradient descent epsilon. Then the theorem says that the limit as epsilon goes to 0 of y is a kernel machine exactly in the form that I showed you before. Okay, so this is interesting, but of course, the most interesting part is, is what the a_i, k, and b are. So, When this happens, what is that kernel? What is the B? What are the AI? Well, the K, as you can guess, is the path kernel as we just defined it. So it's the path kernel associated with the function, with the architecture, if you will, that we're learning, and with the path taken by the parameters during gradient descent. AI is the average derivative of the loss function with respect to the, to the ith class during learning. with a negative sign because we're doing gradient descent. If it was ascent, it would be positive. And b is just the initial model. So what we're doing here is we're adding to the initial model, you know, this series of weighted kernels. So this might seem surprising at first or not. As I said, this result is actually quite simple and including the proof. So I don't know why people didn't think of this before, But there we go. So let me go through the proof because it really is just half a dozen steps or a few more depending on how you count. And the first step is gradient flow. So for those of you not familiar with gradient flow, gradient flow is the continuous version of gradient descent. It's very useful for analysis and there's even, you know, practical algorithms related to it these days. The idea is that we're going to take the continuous limit of the discrete trajectory of gradient descent. So, in particular, gradient flow says that the derivative of the weight vector— remember, W represents a vector, not individual weights— with time is just minus the gradient of the loss function with respect to the weights. And if you want to know where this comes from, just think back to our definition of gradient descent. If you subtract Ws from both sides and divide by epsilon, and then let epsilon go to 0, what you have on the left side is, is the derivative. what you have on the right side is, is the right side of the, um, of the gradient flow equation. Okay, and now we're going to of course draw on the good old chain rule, because after all, that's what backprop is all about. And what that says is that if y is the output, dy/dt is the sum over the weights of the partial derivative of y with respect to the weight times the partial derivative of the weight— sorry, times the derivative of the weight with respect to time. Okay, and notice that conveniently for us, we can also write this as a dot product of 2 vectors. One vector is the gradient of y, and the other vector is the derivative of, of the weight vector. So each component is the derivative of one weight. Okay. And now, looking at these 2 equations, we can, we can substitute dw/dt in the chain rule by its expression given by the gradient flow. And what we get is that dy/dt is just minus this dot product of 2 things, of the gradient of the function and the gradient of the loss. Okay. And notice that even after just these 3 simple steps, this is already starting to look a little bit like, like what we're going for. Okay. Now, next thing, we exploit the additivity of the loss to decompose this into, you know, the same thing over each example. We can, you know, you know, bring the sum outside, and we get this expression that dy/dt is just the sum over the examples of the dot product of the gradient of the function and the gradient of the loss for that example. Now we can apply the chain rule again, because the, the gradient of the loss is its derivative with respect to y times the gradient of y with respect to the examples. I'm going to call the derivative of the loss with respect to y L prime i, just to keep the notation compact. So there it is. And so now we, now we have already here, if you look at it, the tangent kernel, okay, the dot product of the gradient of y, which is the test example, and the gradient of yi, which is a given, any given training example. Okay. And now, of course, our initial model is y0. And what is the final model that we learn going to be? It's just going to be the integral of this, right? So y starts at y0. We know dy/dt. So we integrate. And the final y is y0 minus this integral over the contour of the path of the examples of the sum of the tangent kernels weighted by this average loss derivative. Okay, and now this already pretty much has the form that we want. We can make it a little cleaner, partly, you know, this is a matter of taste at this point, but we can— so what's really missing here to get the expression that I had before is that we need to interchange the integral and the summation, which of course we can do. And then we have the sum over the examples of the path kernel. Which is the integral of the tangent kernel with this L_i prime, which we could decide to make part of the, of the, of the kernel. But, but, you know, in my, for my taste, it's cleaner to just bring it outside by taking its, its average. And it's kind of, I think, also has more intuitive meaning by taking its average over, over, over the course of training. Okay, and so if we do that, we get this expression. That's the first line here. And if you compare that expression with the expression for kernel machine that I stated earlier, you see that they're the same. Okay, in particular, the same with B being y0, the initial model, with ai being the average li prime, the average loss with respect to the ith class over time, and with K being, of course, the path kernel. Okay, so at this point, what we've shown is that at least under this, you know, continuous approximation, what you get when you do gradient descent is, is really a type of kernel machine. Now, there's a few remarks worth making here. Some of them are caveats, some of them are extensions, some of them are interesting relationships to other things. So let me go through those. The first caveat is that if you notice, and again, the notation, you know, obscures that slightly, but the coefficient— this is a little different from, from the typical kernel machine because the coefficients a_i actually depend on, on, on the test example, right? In, in, in a typical kernel machine, they depend on the training examples because they learn But they don't depend on the test example. Okay, but very importantly, they— if you go through this, if you, you know, expand this expression, you will see that everything in this formula only depends on the examples training or testing through the kernels. Okay, and this is the defining property of the kernel machine regardless of the exact form that it takes, and that is still satisfied. Okay, notice also that these AIs actually have a very they have intuitive meaning, which is an example is going to have a high coefficient AI if it has a lot of loss. So if it's a hard example to predict during training, it's going to have a high coefficient, which is exactly the same role that the AIs play in kernel machines and even in simpler things like like the weights of a traditional 1-layer perceptron. Okay. And as I mentioned, if you prefer, you can use a different formulation, which, you know, I call it in the paper the loss-weighted path kernel, where you absorb the losses into the kernel. And then what you have is the a_i's are just -1. So then this is standard in that regard. Now, this kernel in that form is not symmetric, which is a little, you know, again, Not what you expect from a kernel. You can symmetrize it, but, you know, so you can take your pick of whichever of these forms you like best. And often they have, you know, they tell you different things, so they're worth knowing about. Notice also that nothing that I did here depends on the form, on the choice of loss function. So in particular, this applies to least squares. And in fact, in least squares, the AI is actually just the difference. Between the prediction and the actual value, which is kind of what you would expect in least squares regression. And again, illustrates well what is going on here. So the examples with greater error will wind up with greater weight. It also applies to cross-entropy, which for deep learning is the most important thing. For cross-entropy, the a_i's just wind up being -1 over p_i, where p_i is the probability of the class of the ith example. This also applies to density estimation, for example, with, you know, like, you know, this being the likelihood instead of the 1. It's going to be 1 minus 1 over pi, where pi is the probability of the example, and so on. Another thing that some of you might have been wondering is, well, what I did here is for the pure empirical loss, but often in practice we use some regularizer as well. Does this still apply there? Well, yes, it applies very straightforwardly. The regularizer is added, and so at the end of the day, it just winds up being another term being added to B, and that term is a tangent kernel type thing, except that now it's the dot product of the gradient of the regularizer with the gradient of the function for the example, as you might have expected. Okay. Also notice that what I did here was for batch gradient, right? So I'm assuming you take all the examples at once. Of course, in practice, that's not what you do. You do stochastic gradient where you use a mini-batch at a time. The results extend straightforwardly to that case. The demonstration becomes a little bit more complicated, but in essence, what you do is you just need to multiply each example at each step by an indicator function that says, whether the, whether the example is used in the mini-batch at that step or not. So now the integral becomes a stochastic integral, but, you know, but the result is still the same. Here's an interesting observation, which again may have occurred to some of you. This is really a generalization of a classic result from the '60s for single-layer perceptrons. So back in 1964, In the paper that introduced the whole field of kernel machines under the name of the potential function method, this was a paper by Azerman, Braverman, and Rosenauer. One result that they had that I always found fascinating, and I always teach it in my classes, is that they showed that the simple one-layer perceptron, which of course already existed then, is a kernel machine. With dot products as the kernel. It's that simple. Okay, and the reason I find this fascinating is that you look at nearest neighbor, which is really, you know, what, you know, people mostly did at the time, and, you know, nearest neighbor kernel machines are really all, you know, essentially the same thing. You look at nearest neighbor and perceptrons, and they look completely different, but in reality, one is just a simple special case of the other. Okay, and now, of course, and this to me is somewhat enlightening and also somewhat intriguing. And really, you could say that, that the goal of this was try to understand well, or try to figure out, is that result extensible to multi-layer perceptrons? Because if it was, it would be very valuable. And also, there is this history running over the decades, you know, starting in the '60s, '70s, up to now, I would, I would suspect. where people do these amazing things with neural networks, and then somebody comes along and does the same thing with the nearest neighbor kernel machine type algorithm, right? The 2nd wave of neural networks, you know, around 1990, kind of died when, when people were able to do the same thing with kernel machines. They got better results with kernel machines and the convex optimization than that whole horrible mess of trying to use backprop. So if we could do that today, I think you know, the world would be grateful and many billions of dollars in GPUs would be saved. Okay, so this result in a way extends that. And there's also related results like another one that's, I think, salient here, somewhat of a different form but similar in spirit, is if you know or remember, if you're old enough, the second, you know, coming of neural networks in the '80s, it was triggered by Hopfield networks. Okay, this physicist at Caltech that showed this relationship between neural networks and spin glasses, and this led to a huge amount of excitement and so on. But then, you know, Richard Lippmann proved that Hopfield networks, after all their attractor dynamics, blah, blah, blah, blah, they were just nearest neighbor with Hamming distance, which again, in retrospect, is very ironic. You know, maybe people who've known that from the start, they wouldn't have gotten so excited, but maybe it's a good thing they did because then they invented backprop, and Boltzmann machines are just stochastic versions of Hopfield networks, and so on. Okay, so one final important point. Of course, this result assumes that the learning rate is sufficiently small that we can approximate the discrete path of gradient descent by a smooth curve. Okay, and analytically, this, you know, this is a very, you know, pacific thing to do. I think, in fact, if we don't assume that the learning rate goes to 0, we can't even guarantee that gradient will converge. So I think, and, you know, theoretically, this is not controversial. But also, I think in practice, learning rates have to be so small in order to avoid divergence that this approximation, I think, will apply very well. I mean, learning rates of, you know, 10 to the minus 3, 4, 5 are what's typically used. Okay. Nevertheless, you know, it remains an empirical question of how closely, you know, the, you know, the actual learned, you know, deep network, for example, and the corresponding kernel machine will be. But I think at least in terms of the applications and consequences of this, I think this is not that big of a deal. So as I mentioned in the beginning, the most interesting thing about this theorem is the implications. So let's look at what some of them are, and let's start by looking at some of the implications for deep learning, because these days that's what matters most. But then it also has some interesting implications for kernel machines and even for other things like boosting and convex optimization and graphical models and things like that. So So we will also touch on those. So as I alluded, I think the biggest implication/application of this is to the problem of interpretability. People really want to know what is going on in a deep network for debugging purposes. You know, if you're the CEO of a trillion-dollar company and it's dependent on this big black box that could go wrong at any moment, you don't sleep very well. So it'd be nice to understand what is going on in the network. And, you know, there's a whole, you know, literature on that these days. The most popular method is probably to do the following is I try to, you know, I have a prediction for an example. I want to understand why the network made that prediction. For example, if it was a cat and the network said it was a dog, what went wrong? And I look for the nearest example For example, training— nearest training example using Euclidean distance and/or some linearization and so on. And so like, okay, so this is the example that is mainly responsible for the class. Okay, and then gives us— that gives us a hint as to what we need to do to fix the problem, for example. Or it tells, say, the patient why I'm telling her that she has lung cancer, blah, blah, blah. Right now, this is a nice idea, but in practice it tends not to work very well. And now we can understand why. The idea is good, but it's being done in the wrong space. We're not in Euclidean space here. We're in gradient space, right? What we should be doing is finding the closest example or examples in the space of gradients of the architecture, which is really what the path kernel is operating on. Okay? And that— those truly are the examples most responsible for the class. Okay, so this, I think, gives rise to a whole, you know, direction of understanding the behavior and specific predictions of deep networks that we, that we didn't have before. Related to that, there have been over the years these puzzles about the empirical behavior of deep networks that I think this throws some light on. In particular, we have found, as I already alluded to before, over and over again that these networks, even though they look like these very big, powerful, complicated nonlinear models, in practice they often behave very much like nearest neighbor, sometimes exactly like nearest neighbor. And well, here's why, right? Because they are doing— they are kernel machines, right? And also, I mean, these days it's standard that networks will memorize the data, and then people are very surprised that that doesn't cause overfitting, which to me is interesting because it shouldn't be a surprise, right? Memorizing and overfitting are just different things. But exactly how the networks memorize the examples, which, by the way, if you want to do information retrieval, you know, as in some applications of chatbots, that's, that's what you want to do. You want to memorize the data. But how exactly is the data being memorized? Well, this is how it's being memorized, right? I basically just store the examples and I'm applying them, you know, with, with the path kernel, right? So, so that's what really happened here. Also, another very important aspect of the empirical behavior of neural networks is that they are so prone to adversarial examples, right? Why is it that when I move a little bit away from the, from the deep network, I can get, you know, a penguin being classified as a car and the strangest things happening? Well, once you realize that it's a kernel machine and that the curse of dimensionality is operating here, that's not so surprising anymore. But, you know, I will have a little bit more to say that in just a second. And finally, of course, I think this casts some light on this question of representation learning. So I think it's hard to avoid the conclusion looking at this theorem that perhaps, you know, deep networks are not as powerful as representation learners as we thought they were. Okay, it's not that they don't do representation learning. After all, even PCA is doing representation learning, right? Anything that maps your data to a new space is doing representation learning. The question is, how powerful is it? And I think people had this, you know, in particular, you know, some of the, you know, leaders in the field have always had this motivation that, like, we're going to do these amazing things, like, you know, like invent representations. And honestly, it doesn't seem like that's going on. Right? This whole notion that, oh, all the other machine learning methods, they have to draw on hand-coded features, but deep learning doesn't. Well, actually, deep learning does draw on hand-coded features. What are the features? They're the gradients of the architecture, right? It's a particular choice of feature space to work in, one that is actually, as we'll look at shortly, a very smart one, but it's still a choice of features. And that's effectively what's going on here. There's like, you know, it turns out that after all, gradient descent doesn't do magic. Okay, this also means, and, you know, we'll get into that at the end, that, and to me, in some ways, maybe this is the most interesting research question, that if gradient descent is not doing as powerful as representation, the representation learning as powerful as we would like, then what do we need to do? Because after all, human beings do representation learning, and we want representation learning for a lot of things in AI. So how are we going to do that if Backprop as it stands isn't getting us there. So very, I think, very interesting research question. Um, one very interesting, um, view of all this, which again connects deep learning to kernel machines but also to a lot of other things, is that that big black box with a lot of weights and nonlinearities and whatnot, what it really has is a superposition. Of the training examples. In the case of the one-layer perception— this perceptron, this is very obvious. The weight vector is a superposition of the training examples with particular weights, and that's all that the perceptron algorithm did, right? And the power there, and this is a crucial point, is that when I multiply the weight vector by the test example, I'm actually implicitly doing the dot product of the test example with every single one of the training examples. Okay, of course, the cost was that, you know, of using the dot product as the distance function or the similarity functions that, like, now this is not very powerful. All it learns is linear, you know, is hyperplanes, right? But now we can see that the same idea still applies. My black box, which now I have represented as a blue box, it takes the query. And then what is really going on in there is that the query is being compared with each of the training examples by the kernel. And then I weight those kernels and that produces my answer. Okay. And this has some implications for kernel machines also. So for example, you know, starting with the last one here, the thing that really kills kernel machines at the end of the day is that they have a quadratic cost in the size of the training data, right? You have to compute— to train the kernel machine, you have to compute the so-called Gram matrix, right? Right, which is the matrix of the kernel applied to every pair of training examples. And once you have that, you can throw away the data. But the problem is that this is quadratic, right? But if you do it the path kernel way, meaning via backprop, actually now that doesn't happen anymore. You actually— where you used to have this quadratic cost, you actually have now only the linear cost of going through the examples. And also in terms of memory, right, my memory is no longer proportional to the number of support vectors, right? My memory is actually now just a constant, right? It's the— it's the— it's— it's— it's— the memory is just proportional to, roughly speaking, the, the size of the weight vector, right? Which, which is something— it's, it's a design parameter, of course. To learn a more complex function, I will have a longer weight vector and so forth. And, and now at test time, right, used to be that I would have to compare my example with every support vector or every training example, you know, in nearest neighbor and so on. And again, I don't have to do that because I implicitly do all of that in one step by applying this function. Okay, so in terms of, in terms of both training time, test time, and memory cost, this is, you know, a very— using this type of kernel is a very big plus. You, you, you can think of what I'm describing here from the point of view of kernel machines as proposing a new type of kernel called the path kernel. And how to learn it by backprop. And now we're seeing that that has some very desirable properties. One is for scalability. Another very interesting one has to do with incorporating knowledge. You know, like historically over time, there was always this competition, you know, at these— I always saw these people at these research labs. The deep learning people were trying to hack the architecture to get better results, and the kernel machine people were trying to hack the kernel. And at the end of the day, I think a large part of the reason why deep learning networks won out, you know, other than GPUs and so on, is that it is easier to incorporate knowledge into the architecture than into the kernel. It's very flexible in that regard. And so you wind up winning because you've incorporated better knowledge. And what this tells us actually how to incorporate into a kernel machine all the knowledge that we incorporate into a neural network. You want a kernel machine ConvNet, you can do that. You want a kernel machine transformer, you can do that. You want to implement attention, you can do that. I now know how to incorporate attention into a kernel machine using the path kernel. So this, I think, is a very good one. And the third one, of course, is the curse of dimensionality that I touched on earlier. I said, well, you can now see why some of these— some of this brittleness of deep networks comes about. It's because of the curse of dimensionality. But deep networks are less sensitive to the curse of dimensionality than things like nearest neighbor and kernel machines. And now we also understand why, is that they're actually using a much cleverer kernel than, for example, Euclidean distance or a Gaussian kernel, if you will. And think of the following. Suppose that you are trying to learn just the sine function, trying to learn y equals sine of x. Trying to learn that with a Gaussian kernel means you need infinite data. Every time that the sine wave goes up and down, you need another— by Nyquist's theorem, you need twice as many data points as there are cycles the sine wave, right? You'll never be done. Or in practice, if you have, you know, n cycles in your data, you need, you know, 2n examples, give or take. Okay, but if you use the path kernel— and the problem is that in Euclidean space, you know, the only thing that are needed examples are the things that have almost the same value, right? Effectively, right? Unless the function is changing very slow, in which case everything is good. But if the function is changing quickly, as in a fast oscillating sine wave, you're hosed. You're not hosed with the path kernel because now think of the sine wave. The successive— all the peaks are at the same place in gradient space because they all have the same gradient and all the troughs and all points at the same phase in the sine wave are in the same place. So suddenly the amount of data that you need is just what you need to learn one cycle of the sine wave instead of all n you know, potentially infinite cycles of them, right? So this, I think, for kernel machines is just really good news. Now, whether kernel machines can come back from the dead and get a lot of research interest, or that's impossible these days, remains to be seen. But if you judge by what has happened in the past, right, there can be these very fast-paced changes in machine learning where it's all about neural networks one day, and the next day it's all about kernel machines. And the next day it's all about, say, you know, Bayesian learning, which brings us to the next part of the talk, which is implications for other things. Okay, and, and, and, you know, I'll start with, with what is perhaps the most interesting one and one with the most potential for impact, which is you can also look at what I just showed here as saying that deep learning is a form of boosting. Boosting is another of these things that tends to show up in a lot of different places. Well, now it's showing up here. And how is it a form of boosting? The tangent kernel machine, right? You can— I can have a kernel machine where the kernel is the tangent kernel for some weight vector, right, for some network at some point, right? That's my weak learner. And then what this is doing is forming a strong learner by adding with weights a series of these. And each step decreases the error, as it should in boosting. And the coefficient is just epsilon, the learning rate, which will be the same for all of them, which is kind of like a boring version of boosting. But in particular, if you find— if you do a line search, as you often do, to find the best epsilon, now this just becomes a gradient boosting machine. So if you don't like the whole formulation of it's a kernel machine, this path kernel, blah, blah, blah, you can just say, well, The insight here is that deep learning is just boosting the tangent kernel machine. Okay, and again, maybe better ways of doing, you know, deep learning and/or boosting will come out of this. Another interesting consequence is that since everything that is learned by gradient descent is a kernel machine, for example, a Bayesian network whose parameters are learned by gradient descent is a kernel density estimator. Right? Again, it just falls out of this. And it's a kernel density estimator with a particularly clever kernel that incorporates the structure of the Bayesian network, right? It's not like nothing was gained by going from kernel density to Bayesian networks, for example, with respect to the curse of dimensionality, is that we have— we can now incorporate into this kernel all the knowledge of the problem, in particular of conditional independencies, that we incorporate into the Bayesian network. And, you know, there's many other things, but one more that I think is worth mentioning is that If you think about convex learning problems, right, it doesn't actually matter how you solve the problem because the solution is— there's only one, right? It's the global optimum. And so what apply— so what I described here applies to the result of any convex learning, because no matter what algorithm was used to learn it, how fancy or how simple, the result is the same as by doing plain gradient descent, and therefore it has the form that I described here. So again, I think this may give us some insight about convex learning and maybe also help us design better such algorithms, which brings me to the last part of this, which is to mention some possible research directions that come out of this. One that I just alluded to is that my guess is there are new learning algorithms to be had here, some of them very different from deep learning. Some of them may be even very different from current kernel machines, right? The big difference between this and standard kernel machines is that the path kernel is much, much more sophisticated than polynomial kernels or Gaussian kernels and whatnot. And, and, you know, I suspect that there's a lot that can be done there. For example, to make it even easier to incorporate, you know, prior knowledge or assumptions or what have you into your kernel machine, making it more efficient, et cetera, et cetera. Also, looking at this as a piece of research about gradient descent, right? Uh, we can see that maybe there are better ways. So this, this suggests ways in which we might improve gradient descent, in which we might make it, for example, more efficient, in which we might modify it to actually give, give better results in terms of generalization, uh, that, that we might actually be able to, to, you know, to have proofs about, and so on. A very important one, however, is that, and, you know, I touched on that earlier, if we really want to do representation learning, we're not quite there yet. We've made progress, but maybe less progress than we thought we had. So if we really want to learn representations for real, what might we use there, you know, other than backprop, right? Because backprop isn't cut— maybe extensions of backprop, that's one direction, but what are some others? Well, for example, there's predicate invention. Right? In inductive logic programming, you can invent predicates that would let you infer the things that you want to infer. That is potentially a very interesting path to go. In genetic algorithms, you have crossover, which is a non— very non-local operator. Maybe with crossover, we can discover things that we can't with gradient descent. In psychology, right, there's a structure like nearest neighbor and kernel machines are just a very impoverished form of analogy. And there's, you know, there's thousands and thousands of psychology papers showing that humans do reasoning by analogy all the time with everything. And in particular, there's this, this you could call algorithm called structure mapping, where you map the structure from, from your memory to the new problem that has a lot of evidence behind it. And maybe doing structure mapping is a good path for us to do representation learning in machine learning. You know, it's very powerful, right? Things like, you know, Niels Bohr's model of the atom came from a naive, granted, analogy of the atom between the atom and the solar system. And, you know, that was Hofstadter has this whole book with examples of, you know, of, you know, Galois and Einstein and whatnot. All these amazing things that basically came from, from real discoveries in the true sense of discovery that came from doing analogies. So maybe that's one path. Another one that, that I think is a very intriguing one. Is we know coming more from neuroscience is that we know the, the cortex doesn't learn by backprop. Maybe you're, maybe you're, you're, you're cerebellum learns by backprop or something like it, but not, you know, your visual cortex may look somewhat like a ConvNet, but it doesn't learn by backprop. So how, how does it learn? Right? And to the best of our knowledge, the most, or let's say the most promising candidate for how it learns is something called predictive coding. So predictive coding is where, you know, at each point you predict your output, and then the errors in your prediction are what the next layer models. And if that one still makes errors, then you have another layer to model those errors, and so on, right? So this is very powerful. You can learn a lot of things this way. There is increasing evidence from neuroscience that, you know, literally your circuits in your cortex and your thalamus and blah blah are doing predictive coding. This, of course, is still You know, very far from mature, as you know, it's neuroscience, but we can, you know, there are people who work on predictive coding algorithms. They haven't really thought about that in the context of representation learning, but maybe they should. Okay, but lastly, and maybe most interesting for me, and that's certainly where my research since this has focused, is this notion of doing learning based on superpositions of the examples. Okay, this notion that you can remember your data very efficiently and then also access it very efficiently if you— if instead of holding the examples separately, you superpose them all, I think is potentially very powerful. And I might even suspect that, you know, when the field of machine learning is mature, we will realize that that is all we have been doing all along, even with things that are learned, even discrete models learned by combinatorial optimization and whatnot. My intuition, which I can't prove at this point, is that it's all superposition. That's all we've ever been doing. It can be superposition of pieces of examples that you then combine as you do in things like, you know, rule induction logic, inductive logic programming, and so on. But at the end of the day, it's all superposition learning. It's also, I think, has very interesting connections to, for example, quantum computing, right? After all, the whole point of quantum computing is supposed to be that we can do an exponential amount of work In the same time, you can do exponentially more work than a classical computer by taking advantage of superposition. And also, of course, in communications, you know, you send, you know, what reaches your, you know, any receiver is a superposition of a whole bunch of different emissions, but we know how to suss out the ones that we want, right? So I think that this is a very fertile area for research. And in particular, once we've realized this, once we hypothesize that the power of machine learning, and in particular deep networks, comes from superposition, now we can take that as a problem in its own right, right? Like, I don't need to be doing deep learning, right? If really the point is to do superposition learning, what are other ways in which we could do superposition learning? And I think this is potentially a very productive direction of research. So I'll stop there and take questions. Thank you.

Thank you, Pedro. Thank you very much for a thought-provoking talk. So we do have time for questions. We have applause, but I don't know if there are any questions.

There may be some on the chat now.

Yes, there were a lot of comments about the slides not moving,

but I have a question, actually.

Gonçalo, yes, please go ahead.

So in the proof, did I understand correctly, when you pull out this constant, the ai, outside, you are taking a weighted average of the derivative of the li? So it's a weighted average that comes out, right? And it's weighted by the gradient of y, in turn, gradient of yi. Yeah, I see.

Yes, exactly.

So the kernel is going to be the integral over the path Of the gradient of y, gradient of, in turn, with the gradient of yi.

Yes, of tangent kernel. Yes, it's not the gradient. It's the dot product of the kernels. But yes.

So this depends a lot on the path, which itself depends on where you start.

Absolutely.

So it's not clear. It's not clear to me, for the same model, if you start in a different, at a different set of weights, learning that the kernel is going to be anything similar to if you started somewhere else. I think—

No, on the contrary. On the— no.

Okay.

Okay. So let me clarify that. On the contrary, you will wind up somewhere different. In fact, one of the things that this makes you realize, if you hadn't already, which, you know, ideally you should have, is that the initialization is extremely important. In fact, I would even say that half of the work in deep learning is done by the initialization. You start from a different point, you get a different thing. And you can start in very different— and we know that empirically, right? You start in different basins of attraction, you get dramatically different results depending on where you start, right? Notice also a very important point here, which sort of like may not— you may not notice at first, is that nothing I did here depends at all on the convergence of the algorithm. A lot of the analysis with tangent kernels are done at the initialization point. Right? That's where the analysis is done.

Yes, but here you have to be able to make this integral. So—

No. Yeah, yeah. No. And so, but, um, and now I do this integral, right? And this, the treatment that I do is valid no matter where I integrate from and to, right? So I don't have to integrate to convergence, right? I can say I'm going to run this for 100 steps, and what I said here applies. Right. It's not going to be optimal with respect to loss function, but your deep network is still going to be a kernel machine.

Yeah. Yeah. So I think the appeal of this, of the neural networks compared, is that you don't have to worry about the kernel. It's going to pick some very nonlinear kernel. It's not going to be a linear kernel regression, some kind of kernel machine, but you don't have to worry about the kernel. And it's going to cook up a kernel that hopefully is good.

Well, what I would say, right, is that, well, the message— I mean, this is a key point, right? It's like, what is the, you know, like, in the light of this, for example, why shouldn't I just go do kernel machines instead, right? So the appeal of deep learning hasn't always been empirical. It works very well in practice, right? And I think this helps elucidate why it is and why it isn't working. And now Compared to kernel machines deep learning, as I alluded to, it has enormous advantages in terms of scalability, which is really important. So the key difference is this superposition notion, is that I don't have to store the examples individually and incur the huge memory and time cost that that represents. I don't have to compute— I mean, I can— the appeal of deep learning, you could say, is that I can do kernel machine learning without computing the Gram matrix. Right, which sounds like that can't be right, but it is, right? So you could also say now, now I don't— so you could say, well, I don't have to worry about the kernel. I actually think I would take that the other way, is that like knowing what's going on with the kernel is actually a plus, right? The disadvantage of deep learning is that I don't know what's going on there. Now that I know that what's going on is the path kernel, suddenly a lot of stuff becomes more transparent. And in particular for us, the researchers, it becomes easier and faster To develop, to do improvements, right? Because we understand what's going on.

Yeah, so it might be interesting to explore some examples to see how this path kernel looks in some easy examples, I guess.

Yeah, for sure.

OK, thank you. That was all the questions I have.

Thank you. I have a question, Pedro. So you, along in the derivation, you use derivatives of the loss with respect to the yi's. Which rules out anything that's discrete labels, stuff like that, right? Because you cannot compute derivatives of a loss with respect to categories.

No, well, remember, the only condition here is that the loss function has to be differentiable. And for example, what I mean, this is just standard, right? Like,

differentiable with respect to— but you said, yeah, you mentioned that the function does not have to be differentiable with respect to the input. That's okay. But the loss needs to be differentiable with respect to the parameters, of course, otherwise you could not do gradient descent. But then you use gradients of the loss with respect to the labels, to the y's.

No, yeah, let me clarify.

What

does that mean? Yeah, yeah, no, yes. So if you're doing this for clarification, my y's, like, are the— it's the log probability of the class. Again, I'm not doing anything—

Yeah, the y in the test example, yes, because you can think of the the machine as producing probabilities of the classes, but the yi's, they're just labels, just categories.

No, yes, but you can think of the yi's— again, again, I'm not inventing anything here— that they're just samples from the probability, right? So they are not— so like the under— so let me answer your question very directly.

But they're not quantities.

The underlying continuous quantity here that is continuous is the probability of the class.

True, right? No problem. But the yi's— so if you write the log loss, the probability that the output of the network is a number, you can compute gradients with respect to it. But the labels are not. The labels are categories. You cannot differentiate with respect to categories. What did it mean?

No, no, but no, I mean, so notice also that what I'm doing here, like, again, the PowerPoint notation is obscuring what's going on here, right? But like, All I'm doing, though, is I'm just computing an average that is weighted by the kernels. So I don't have the— let me pull up— well—

Yeah, I'm looking at the paper.

The paper has this more clearly than—

I'm looking at your paper, and you have in the big— some summation, and then you said dl, so partial L partial yi. And my question is, what is partial L partial yi? When, as I said, categories, are you thinking about one-hot representation and you're computing derivative with respect to—

no, no, no, no, like, like, think of—

then you need to compute the derivative in the simplex, which is not so easy because it's, it's not—

I mean, so if you go to the remarks and where I describe how this very briefly, how this applies to different loss functions, your yi in this treatment is not yi the label, it's pi, the probability of that label.

Okay,

right. And then it all goes through. It's a continuous query.

Okay, got it. Okay, but, but so it did. But anyway, it excludes stuff like zero and loss, for example.

Yeah, sure.

Okay, okay.

Yeah,

the other thing is the— in the, in the, in the, in the picture where you have the blue box, don't you think that it's a bit misleading because of the fact that the A's also Depend on the query. And so the picture is actually much more complicated than that.

No, I mean, of course, you know, this is a PowerPoint. All PowerPoints—

Come on, you could, you could have written A1 of query. It would be easy.

No, I mean, look, uh, of course, uh, there are more, uh, um, edges and boxes in this diagram than I'm, that I'm showing here. But, you know, by the time you see this box, you know what they are. But you're right. I mean, this is an oversimplification, but nevertheless, What is here is true. It's just not the complete picture, which would require another level of

discussion. My point is that the picture kind of suggests that this is a linear combination of the kernel values when it's—

Oh, no, no, no, no, no, no, no, not linear.

Yeah, so that's very important.

I didn't say linear. No, no.

I know, but it's kind of hidden behind the fact that you drop the dependency of the a's on the query. If you look at these without context—

I mean, fair enough. I could have put there a1 of q or of x, blah, blah, blah, blah. Yeah. Again, look, I have K there, right? You know that it's K of x, x prime, right? So yes.

Yeah.

No, I mean, you're right. It's important to keep these dependencies in mind so that you know what's going on.

So that you don't oversell what— it's not oversimplifying.

Yeah. But also, I mean, like, it's— I would take it the other way, is that if this was linear, it would not be as interesting, right? So the fact that this AI is a function of the input is actually—

But in this case, it's not. But being nonlinear is not as useful. Right, it's more interesting but not as useful because you're just kind of rewriting a complicated nonlinear dependence in a particular way. And, uh, yeah.

No, I mean, no, on the contrary, like what I'm doing— again, this is my own subjective view— but like what I'm doing here that's very useful is that I'm writing a complicated nonlinear dependence as something that is more transparent. In particular, what this is pulling out, and that's the, the goal really, is The role is the fact that how am I memorizing the examples and then using them, right? It's not obvious when you look at a deep network how and where it's storing the examples and then what it's doing with them. And, you know, using the path kernel, we can see what's happening here. There is this kernel, the path kernel, that's comparing the new example with the training ones, and then it's being multiplied by these— you can call them these other functions that also do other things. But so this is not all that's going on, but I think it's enlightening as part of what's going on.

Let me get— let me just— one last question. I don't know, I don't want— I don't want to monopolize the discussion. Any other questions? So, Tiago has one question.

Okay, so Pedro, just— it's not really— well, it is a question, but is— would it be fair to say that if you're using conventional kernel machines, your representation is fixed a priori, and so the power of what A posteriori, what you would say is the power of deep learning, you are still in a sense coming up with a new representation that wasn't there. It's just that the representation can be seen as a kernel machine, but endogenously created.

Thank you for asking that question. I should have mentioned this in the talk, right? There's a very important point here, which is the following. Right at the beginning, when I introduced kernel machines, I should have mentioned that With the kernel machines that I typically use have fixed kernels, okay, like Gaussian, polynomial, but you can also learn the kernel. In fact, there's a whole subfield of kernel machines that's how to learn kernels. Like Corinna—

It doesn't work very well.

No, exactly, that was my next sentence, was that it tends not to work very well in practice. So absolutely, you know, what is happening here is that a deep network is a kernel machine with a learned kernel The learned kernel is the path kernel, and that is precisely where its power is. So from the point of view of kernel machines, you can look— this is like, ah, here's a way that we didn't know we had, but we do, of learning kernels that actually works really well in practice, whereas the previous methods didn't. So yeah, thank you for the question.

Any other questions?

Hi, I'll ask a very naive one. At some point in the— at the very beginning, you threw away the activation function. Is there a reason for this? It was just a PowerPoint notation?

The final—

No, I mean, so to go back to that, what is this activation typically? For example, if you're doing a class prediction, you just pass it through a step function, okay? Or a sigmoid, or maybe one of the probability— So, so the— this doesn't change anything about, you know, about the treatment that I have here. Okay, again, in some applications you don't need— I mean, like, you often see in textbooks people don't even have that G there, but that G is an option.