Foundations and Challenges of Deep Learning (Yoshua Bengio)

Thank you, Sami. So I'll tell you about some very high level stuff today. And no new algorithm. Some of you already know about the book that Ian Goodfellow, Aaron Courville and I have written and it's now in pre sale by MIT Press. I think you can find it on Amazon or something. And paper. The actual shipping is going to be in December, hopefully for nips. So we've already heard that story at least, well from several people here, at least from Andrew I think. But it's good to ponder a little bit some of these ingredients that seem to be important for deep learning to succeed. But in general for machine learning to succeed, to learn really complicated tasks of the kind we want to reach human level performance. So if a machine is going to be intelligent, it's going to need to acquire a lot of information about the world. And the big success of machine learning for AI has been to show that we can provide that information through data, through examples. But really think about it, that machine will need to know a huge amount of information about the world around us. This is not how we are doing it now because we're not able to train such big models, but it will come one day. And so we'll need models that are much bigger than the ones we currently have. Of course that means machine learning algorithms that can represent complicated functions. That's one good thing about neural nets. But there are many other machine learning approaches that allow you in principle to represent very flexible forms like non parametric methods, classical nonparametric methods or SVMs. But they're going to be missing 0.4 and potentially 0.5 depending on the methods. 0.3. Of course you need enough computing power to train and use these big models. And 0.5 just says that it's not enough to be able to train the model, you have to be able to use it in a reasonably efficient way from a computational perspective. This is not always the case with some probabilistic models where inference, in other words, answering questions, having the computer do something can be intractable and then you need to do some approximations which could be efficient or not. Now the point I really want to talk about is the fourth one. How do we defeat the curse of dimensionality? In other words, if you don't assume much about the world, it's actually impossible to learn about it. I'm going to tell you a bit about the assumptions that are behind a lot of deep learning algorithms which make it possible to work as well as we are seeing in practice in the last few years. Something wrong. Microsoft bug. Ok, so how do we bypass the curse of dimensionality? The curse of dimensionality is about the exponentially large number of configurations of the space variables that we want to model. The number of values that all of the variables that we observe can take is going to be exponentially large in general, because there's a compositional nature. If each pixel can take two values and you got a million pixels, then you got 2 to 1 million number of possible images. So the only way to beat an exponential is to use another exponential. So we need to make our models compositional. We need to build our models in such a way that they can represent functions that look very complicated, but yet these models need to have a reasonably small number of parameters. Reasonably small in the sense that compared to the number of configurations of the variables, the number of parameters should be small. And we can achieve that by composing little pieces together, composing layers together, composing units on the same layer together. And that's essentially what's happening with deep learning. So you actually have two kinds of compositions. There's the compositions happening on the same layer. This is the idea of distributed representations, which I'm going to try to explain a bit more. This is what you get when you learn embeddings for words or for images, representations in general. And then there is the idea of having multiple levels of representation. That's the notion of depth. And there there's another kind of composition that takes place. Whereas the first one is a kind of parallel composition. I can choose the values of my different units separately and then they together represent an exponentially large number of possible configurations. In the second case, there's a sequential composition where I take the output of one level and I combine them in new ways to build features for the next level, and so on and so on. So the reason deep learning is working is because the world around us is better modeled by making these assumptions. It's not necessarily true that deep learning is going to work for any machine learning problem. In fact, if we consider the set of all possible distributions that we would like to work from, deep learning is no better than any other. And that's basically what the no free lunch theorem is saying. It's because we are incredibly lucky that we live in this world, which can be described by using composition, that these algorithms are working so well. This is important to really understand this. So before I go a bit more into distributed representations, let me say a few words about non distributed representations. So if you're thinking about things like clustering N grams for language modeling, classical nearest neighbors SVMs with Gaussian kernels, classical non parametric models with local kernels, decision trees, all these things. The way these algorithms really work is actually pretty straightforward. If you cut the crap and hide the math and try to understand what is going on. They look at the data in the data space and they break that space into regions and they're going to use different free parameters for each of those regions to figure out what the right answer should be. The right answer, it doesn't have to be supervised learning. Even in unsupervised learning there's a right answer. It might be the density or something like that. Okay. And you might think that that's the only way of solving a problem. We consider all of the cases and we have an answer for each of the cases and we can maybe interpolate between those cases that we've seen. The problem with this is somebody comes up with a new example which isn't in between two of the examples. We've seen something that requires us to extrapolate something that's non trivial generalization, and these algorithms just fail. They don't really have a recipe for saying something meaningful. Away from the training examples. There's another interesting thing to note here which I would like you to keep in mind before I show the next slide, which is in red here, which is we can do a kind of simple counting to relate the number of parameters, the number of free parameters that can be learning, and the number of regions in the data space that we can distinguish. So here we basically have a linear relationship between these two things. So for each region I'm going to need at least something like some kind of center for the region. And maybe if I need to output something, I'll need an extra set of parameters to tell me what the answer should be in that area. So the number of parameters grows linearly with the number of regions that I'm going to be able to distinguish. The good news is I can have any kind of function, so I can break up the space in any way I want. And then for each of those regions I can have any kind of output that I need. So for decision trees the regions would be splitting across axes and so on. And for this is more like for nearest neighbor or something like that now. Ah, another bug. I don't think I will send. Let's hope it works this time. Oh, I have another option. Sorry about this. Okay, so here's the point of view of distributed representations for solving the same general machine learning problem. We have a data space and we want to Break it down. But we're going to break it down in a way that's not general. We're going to break it down in a way that makes assumptions about the data, but it's going to be compositional and it's going to allow us to be exponentially more efficient. So how are we going to do this? So in the picture on the right, what you see is a way to break the input space by the intersection of half planes. And this is the kind of thing you would have with what happens at the first layer of a neural net. So here, imagine the input is two dimensional. So I can plot it here, and I have three binary hidden units. C1, C2, C3. So because they're binary, you can think of them as little binary classifiers. And because it's only a one layer net, you can think of what they're doing as a linear classification. And so those colored hyperplanes here are the decision surfaces for each of them. Now, these three bits, they can take eight values corresponding to whether each of them is on or off. And those different configurations of those bits correspond to actually seven regions here, because there is one of the eight regions, which is not feasible. So now you see that we are defining a number of regions which is corresponding to all of the possible intersections of the corresponding half planes. And now we can play the game of how many regions do we get for how many parameters? And what we see is that if we played the game of growing the number of dimensions of features and also of inputs, we, we can get an exponentially large number of regions which are all of these intersections. There's an exponential number of these intersections corresponding to different binary configurations. Yet the number of parameters grows linearly with the number of units. So it looks like we're able to express a function. And then on top of that, I could imagine you have a linear classifier that's the one hidden layer neural net. So, so the number of parameters grows just linearly with the number of features, but the number of regions that the network can really provide a different answer to grows exponentially. So this is very cool. And the reason it's very cool is that it allows those neural nets to generalize, because while we're learning about each of those features, we can generalize to regions we've never seen, because we've learned enough about each of those features separately. I'm going to give you an example of this in a couple of slides, actually. Let's do it first. So think about those features. Let's say the input is an image of a person, and think of those features as things like, I have a detector that says that the person wears glasses, and I have another unit that's detecting that the person is a female or male. And I have another unit that detects that the person is a child or not. And you can imagine hundreds or thousands of these things, of course. So the good news is you could imagine learning about each of these feature detectors, these little classifiers, separately. In fact, you could do better than that. You could share intermediate layers between the input and those features. But let's take even the worst case and imagine we were to train those separately, which is the case in the linear model that I showed before. We have a separate set of parameters for each of these detectors. So if I have N features, each of them, say, needs order of k parameters, Then I need order of n k parameters, and I need order of NK examples. And one thing you should know from machine learning theory is that if you have order of p parameters, you need order of p examples to do a reasonable job of generalizing. You can get around that by regularizing and effectively having less degrees of freedom. But to keep things simple, you need about the same number of examples or maybe say, 100 times more or 10 times more as the number of really free parameters. So now the relationship between the number of regions that I can represent and the number of examples I need is quite nice because the number of regions is going to be two to the number of features of these binary features. So, you know, a person could wear glasses or not be a female or a male or child or not, and I could have 100 of these things, and I could probably recognize reasonably well all of these two to the 100 configurations of people, Even though I've obviously not seen all of those 2 to 100 configurations. Why is it that I'm able to do that? I'm able to do that because the models can learn about each of these binary features kind of independently, in the sense that I don't need to see every possible configuration of the other features to know about wearing glasses. Like, I can learn about wearing glasses even though I've never seen somebody who was a female and a child and chubby and had yellow shoes, and I have seen enough examples of people wearing glasses, I can learn about wearing glasses in general. I don't need to see all of the configurations of the other features to learn about one feature. Okay? And so this is really why this thing works, is because we're making assumptions about the data that those features are meaningful. By themselves, and you don't need to actually have data for each of the regions, the exponential number of regions, in order to learn the proper way of detecting or discovering these intermediate features. Let me add something here. There were some experiments recently actually showing that this kind of thing is really.