CS231n Winter 2016: Lecture 2: Data-driven approach, kNN, Linear Classification 1

And we're recording as well? Okay, great. Just to remind you again— hello— we're recording the classes, so if you're uncomfortable speaking in front of the camera, you're not in the picture, but your voice might be on the recording. Okay, great. As you can see also, the screen is wider than it should be, and I'm not sure how to fix it, so we'll have to live with it. Luckily, your visual cortex is very good. It's very invariant to stretching, so this is not a problem. OK, so we'll start out with some administrative things before we dive into the class. The first assignment will come out tonight or early tomorrow. It is due on January 20, so you have exactly 2 weeks. You will be writing a k-nearest neighbor classifier, a linear classifier, and a small 2-layer neural network. And you'll be writing the entirety of backpropagation algorithm for a 2-layer neural network. We'll cover all that material in the next 2 weeks. Warning, by the way, there are assignments from last year as well, and we're changing the assignments. So please do not complete a 2015 assignment. That's something to be aware of. And for your computation, by the way, we'll be using Python and NumPy. And we'll also be offering terminal.com, which is basically these virtual machines in the cloud that you can use if you don't have a very good laptop and so on. I'll go into detail of that in a bit. I'd just like to point out that for the first assignment, We assume that you'll be relatively familiar with Python, and you'll be writing these optimized NumPy expressions where you're manipulating these matrices and vectors in very efficient forms. So for example, if you're seeing this code and it doesn't mean anything to you, then please have a look at our Python NumPy tutorial that is up on the website as well. It's written by Justin, and it's very good. And so go through that and familiarize yourself with the notation because you'll be writing a lot of code that looks like this, where we're doing all these optimized operations so that they're fast enough. To run on a CPU. Now in terms of terminal, basically what this amounts to is that we'll give you a link to the assignment. You'll go to a web page, and you'll see something like this. This is a virtual machine in the cloud that has been set up with all the dependencies of the assignment. They're all installed already. All the data is already there. And so you click on Launch a Machine, and this will basically bring you to something like this. This is running in your browser. And this is basically a thin layer on top of an AWS machine, a UI layer here. And so you have an iPad, a notebook, and a little terminal, and you can go around, and this is just like a machine in the cloud. And so they have some CPU offerings, and they also have some GPU machines that you can use, and so on. You normally have to pay for terminal, but we'll be distributing credits to you. So you just email us to a specific TA that we'll decide in a bit. You email to a TA, and you ask for money. We'll send you money, and we keep track of how much money we've sent to all the people, so you have to be responsible with the funds. So this is also an option for you to use if you like. OK, any details about this? Yeah, go ahead. A quick question. You said that they have GPU units. Does that mean we can write PyCuda code, or is that not acceptable? You can write it if you like. It's not required for the assignment, but you can probably get that to run, yeah. OK, great. So I'm just going to dive into the lecture now. Today we'll be talking about image classification, and especially we'll start off on linear classifiers. So when we talk about image classification, the basic task is that we have some number of fixed categories, say dog, cat, truck, plane, or so on. We get to decide what these are. And then the task really is to take an image, which is a giant grid of numbers, and we have to transform it to one of these labels. We have to bin it into one of the categories. This is the image classification problem. We'll spend most of our time talking about this one specifically. But if you'd like to do any other task in computer vision, such as object detection, image captioning, segmentation, or whatever else, you'll find that once you know about image classification and how that's done, everything else is just a tiny delta on top of it. So you'll be in a great position to do any of the other tasks. So it's really good for conceptual understanding, and we'll work through that as a specific example, uh, to simplify things in the beginning. Now, why is this problem hard? Just to give you an idea, the problem is what we refer to as a semantic gap. This image here is a giant grid of numbers. The way the images are represented in the computer is is that this is basically, say, roughly a 300 by 100 by 3 pixel array, so 3-dimensional array, and the 3 is for the 3 color channels, red, green, and blue. And so when you zoom in on a part of that image, it's basically a giant grid of numbers between 0 and 255. Uh, so that's what we have to work with. These numbers indicate the amount of brightness in all the 3 color channels at every single position in the image. And so the reason that image classification is difficult is when you think about —what we have to work with, these, like, millions of numbers of that form, and having to classify things like cats, it quickly becomes apparent the complexity of the task. So for example, the camera can be rotated around this cat, and it can be zoomed in and out and rotated, shifted. The focal properties, intrinsics of that camera can be different. And think about what happens to the brightness values in this grid as you actually do all these transformations with the camera. It'll completely shift. All the patterns are changing, and we have to be robust to all of this. There's also many other challenges. For example, challenges of illumination. Here we have a long cat, uh, one cat. We actually have two of them, but you almost can't see the other one. And so one cat is basically illuminated quite a bit and the other is not, but you can still recognize two cats. And so think about, again, the brightness values on the level of the grid and what happens to them as you change all the different lightings and all the possible lighting schemes that we can have in the world. We have to be robust to all of that. There's issues of deformation, many classes, lots of strange arrangements of all of these objects we'd like to recognize. So cats coming in very different poses. By the way, the slides, when I create them, they're quite dry. There's a lot of math and so on. So this is the only time I get to have fun. So that's why I just pile everything with cat pictures. So we have to be robust to all of these deformations. You can still recognize that there's a cat in all of these images despite its arrangement. There's problems of occlusion. So sometimes we might not see the full object, but you still recognize that's a cat behind the curtain. That's a cat behind a water bottle. And there's also a cat there inside a couch, even though you're seeing just tiny pieces of this class, basically. There's problems of background clutter. So things can blend into the environment. We have to be robust to that. And there's also what we refer to as intra-class variation. So cat— actually, there's a huge amount of cats. Just species, and so they can look different ways. We have to be robust to all of that. So I'd just like you to appreciate the complexity of the task. When you consider any one of these independently, it's difficult. But when you consider the full cross-product of all these different things and the fact that our algorithms have to work across all of that, it's actually quite amazing that anything works at all. In fact, not only does it work, but it works really, really well, almost at human accuracy. We can recognize thousands of categories like this, and we can do that in a few dozen milliseconds. With the current technology, and so that's what you'll learn about in this class. So what does an image classifier look like? Basically, we're taking this 3D array of pixel values. We'd like to produce a class label. And what I'd like you to notice is that there's no obvious way of actually encoding any of this— of these classifiers, right? There's no simple algorithm. Like, say you're taking an algorithms class in your early computer science curriculum. You're writing bubble sort, or you're writing something else to do any particular task. You can intuit all the possible steps, and you can enumerate them and list them and play with it and analyze it. But here there's no algorithm for detecting a cat under all these variations, or it's extremely difficult to think about how you'd actually write that up. What is the sequence of operations you would do on an arbitrary image to detect a cat? That's not to say that people haven't tried, especially in the early days of computer vision. There were these explicit approaches, as I'd like to call them, where you think about, okay, a cat, say, is a— we'd like to maybe look for little earpieces. So what we'll do is we'll detect all the edges, we'll trace out edges, we'll classify the different shapes of edges and their junctions. We'll create, you know, libraries of these and we'll try to find their arrangements, and if we ever see anything ear-like, then we'll detect a cat. Or if we see any particular texture of some particular frequencies, we'll detect a cat. And so you can come up with some rules. But the problem is that once I tell you, okay, I'd like to actually recognize a boat now, or a person, then you have to go back to the drawing board and you have to be like, okay, what makes a boat? Exactly what's the arrangement of edges, right? It's a completely unscalable approach to classification. And so the approach we're adopting in this class and the approach that works much better is the data-driven approach that we like in the framework of machine learning. And just to point out that in these days, actually in the early days, they did not have the luxury of using data because at this point in time, you're taking grayscale images of very low resolution. You have 5 images and you're trying to recognize things. It's obviously not going to work. But with the availability of internet, huge amount of data, I can search, for example, for cat on Google, and I get lots of cats everywhere. And we know that these are cats based on the surrounding text in the web. Pages. And so that gives us lots of data. So the way that this now looks like is that we have a training phase where you give me lots of training examples of cats and you tell me that they're cats, and you give me lots of examples of any type of other category you're interested in. I do— I go away and I train a model. A model is a class, and I can then use that model to actually classify new test data. So when I'm given a new image, I can look at my training data and I can do something with this based on just the pattern matching. and statistics and so on. So as a simple, uh, first example we'll work with in this framework, consider the nearest neighbor classifier. The way nearest neighbor classifier works is that effectively we're given this giant training set. What we'll do at training time is we'll just remember all of the training data. So I have all the training data, I just put it here and I remember it. Now when you give me a test image, what we'll do is we'll compare the test image to every single one of the images we saw in the training data, and we'll just transfer the label over. So I'll just look through all the images. Um, we'll work with specific case as I go through this. I'd like to be as concrete as possible. So we'll work with a specific case of something called CIFAR-10 dataset. The CIFAR-10 dataset has 10 labels. These are the labels. There are 50,000 training images that you have access to, and then there's a test set of 10,000 images where we're going to evaluate how well the classifier is working. And these images are quite tiny. They're just little toy dataset of 32 by 32 little thumbnail images. So the way nearest neighbor classifier would work is we take all this training data that's given to us, 50,000 images. Now at test time, suppose we have these 10 different examples here. These are test images along the first column here. What we'll do is we'll look up nearest neighbors in the training set of things that are most similar to every one of those images independently. So there you see a ranked list of images that are most similar to in the training data to any one of those 10— to every one of those test images over there. So in the first row, we see that there's a truck, I think, as a test image, and there's quite a few images that look similar to it. We'll see how exactly we define similarity in a bit. But you can see that the first retrieved result is in fact a horse, not a truck, and that's because of just the arrangement of the blue sky that was throwing it off. So you can see that this will not probably work very well. Now, how do we define the distance metric? How do we actually do the comparison? There are several ways. One of the simplest ways might be a Manhattan distance. So an L1 distance or Manhattan distance, I'll use the two terms interchangeably, simply what it does is you have a test image you're interested in classifying and consider one single training image that we want to compare this image to. Basically what we'll do is we'll element-wise compare all the pixel values. So we'll form the absolute value differences and then we just add all of it up. So we're just looking at every single pixel position, we're subtracting it off and seeing what the differences are at every single spatial position. Adding it all up, and that's our similarity. So these two images are 456 different. Okay? So we'll get a 0 if we have identical images here. Just to show you code specifically, uh, the way this would look like, this is a full implementation of a nearest neighbor classifier in NumPy and Python, um, where I filled in the actual body of the two methods that I talked about. And basically what we do here at training time is we're given this dataset X, the images, and Y, which usually denote the labels. So we're given images and labels. All we do is just assign to the class instance methods. So we just remember the data. Nothing is being done. At predict time though, what we're doing here is we're getting new test set of images X. And I'm not going to go through full details, but you can see that there's a for loop over every single test image independently. We're getting the distances to every single training image. And notice that that's only a single line of vectorized Python code. So in a single line of code, we're comparing that test image to every single training image in the database, and we're computing this distance in a previous slide in a single line. Okay? So that's vectorized code. We didn't have to expand out all those for loops that are involved in processing this distance. And then we compute the instance that is closest. So we're getting the min index. So that's the index of the training example that is— has the lowest distance. And then we're just predicting for this image the label of whatever was nearest. So here's a question for you in terms of the nearest neighbor classifier. How does its speed depend on the training data size? What happens as I scale up the training data? It's slower? OK. Yes. It's actually— it's in fact linearly slower, right? Because if I have— I just have to compare to every single training example independently. So it's a linear slowdown. And you'll notice actually as you go— as we go through the class is that this is actually backwards because what we really care about in most practical applications is we care about the test time performance of these classifiers. That means that we want this classifier to be very efficient at test time. And so there's this trade-off between really how much compute do we put in the train method and how much compute do we put in a test method. A nearest neighbor is instant at train but then it's expensive at test. And as we'll see soon, ConvNets actually flip this completely the other way around. We'll see that we do a huge amount of compute at train time. We'll be training a convolutional neural network. But the test time performance will be super efficient. In fact, it will be constant amount of compute. For every single test image, we'll do constant amount of computation. No matter if you have a million, billion, or trillion training images— I'd like to have a trillion training images— no matter how large your training dataset is, we'll do a constant compute to classify any single testing example. So that's very nice, practically speaking. Now, I'd just like to point out that there are ways of speeding up nearest neighbor classifiers. There's these approximate nearest neighbor methods. FLAN is an example library that people use often in practice that allows you to speed up this process of nearest neighbor matching. But that's just a side note. OK. So let's go back to the design of the nearest neighbor classifier. We saw that we've defined this distance. And I've arbitrarily chosen to show you the Manhattan distance. Which compares the difference of the absolute values. There's in fact many ways you can formulate a distance metric, and so there's many different choices of exactly how we do this comparison. Another choice that people like to use in practice is what we call the Euclidean or L2 distance, which instead sums up the differences in the sums of squares of these differences between images. And so this choice— what happened there? Did someone push a button over there in the back? Andrej Karpathy. Okay, thank you. So this choice of what— how exactly we compute a distance, it's a discrete choice that we have control over. That's something we call the hyperparameter. It's not really obvious how you set it. It's a hyperparameter. We have to decide later on exactly how to set this somehow. Another sort of hyperparameter that I'll talk about in context of nearest neighbor classifier is when we generalize nearest neighbor to what we call a k-nearest neighbor classifier. So in a k-nearest neighbor classifier, instead of retrieving for every test image the single nearest training example, we'll in fact retrieve several nearest examples and we'll have them do a majority vote over the classes to actually classify every test instance. So say a 5-nearest neighbor, we would be retrieving the 5 most similar images in the training data and doing a majority vote of the labels. Here's a simple 2-dimensional dataset to illustrate the point. So here we have a 3-class dataset in 2D. Here I'm drawing what we call decision regions of this nearest neighbor classifier here. What this refers to is we're showing the training data over there and we're coloring the entire 2D plane by what class this nearest neighbor classifier would assign at every single point. Suppose you, suppose you had a test example somewhere here, then this is just saying that this would have been classified as blue class based on the nearest neighbor. You can, for example, note that here is a point that is a green point inside the blue cluster. and it has its own little region of influence where it would have classified a lot of test points around it as green because if any point fell there, then that green point would have been the nearest neighbor. Now when you move to higher numbers for K, such as 5 nearest neighbor classifier, what you find is that the boundaries start to smooth out. It's kind of this nice effect where even if there is this one point kind of randomly as a noise, an outlier in the blue cluster, it's actually not influencing the predictions too much. Because we're always retrieving 5 nearest neighbors, and so they get to overwhelm the green point. So in practice, you'll find that usually k-nearest neighbor classifiers offer better, better performance at test time. Now, but again, the choice of k is again a hyperparameter, right? So I'll come back to this in a bit. Just to show you an example of what this would look like, here I'm retrieving 10 most similar examples. They're ranked by their distance, and I would actually do a majority vote over these training examples here. To classify every test example here. Okay. So let's do a bit of, uh, questions here just for fun. Uh, consider what is the accuracy of the nearest neighbor classifier on the training data when we're using Euclidean distance? So suppose our test set is exactly the training data and we're trying to find the accuracy. In other words, how many— how often would we get the correct answer? 100%. 100%? Good. Why? [INAUDIBLE] OK. Among the murmurs, yeah, that's correct. So we always find a training example exactly on top of that test, which has 0 distance. And then its label will be transferred over. Good. What if we're using the Manhattan distance instead? So Manhattan distance doesn't use sum of squares. It uses sum of absolute values of differences. Wouldn't it be the same? It would. It's just a trick question. It would be the same. OK, good. So we're keeping— paying attention here. OK, what is the accuracy of the k-nearest neighbor classifier on the training data then? Say k was 5. Is it 100%? No. Not necessarily, right? Good. Because basically the points around you could overwhelm you even if you're best example is actually of a different class. Okay, good. So we've discussed two choices of different, here, hyperparameters. We have the distance metric, it's a hyperparameter, and this K, we're not sure how to set it. Should it be 1, 2, 3, 10, and so on. So we're not exactly sure how to set these. In fact, they're problem dependent. You'll find that you can't find a consistently best choice for these hyperparameters. In some applications, some K might look— might work better than other applications. So we're not really sure how to set this. So here's an idea. We have to basically try out lots of different hyperparameters. So what I'm going to do is I'm going to take my train data, and then I'm just going to try out lots of different hyperparameters. So I have my test data, and I try out k equals 1, 2, 3, 4, 5, 6, 20, 100. I try out all the different distance metrics, and whatever works best, that's what I'll take. So that will work very well, right? No. It won't work very well? Why is it not going to— why is this not a good idea? Because you will fail to generalize on unseen data. OK. So basically— That's— if you correctly fit to that. So basically, yes. So test data is your proxy for your generalization of your algorithm. You should not test the test data. In fact, you should forget that you ever have test data. So once you're given your data set, always set aside the test data. Pretend you don't have it. That's telling you how well your algorithm is generalizing to unseen data points. And this is important because you're trying to develop your algorithm, and then you're hoping to eventually deploy it in some setting. And you'd like to have an understanding of exactly how well do I expect this to work in practice, right? And so you'll see that, for example, sometimes you can perform very, very well on training data but not generalize very well to test data when you're overfitting and so on. And a lot of this, by the way, 229 is a requirement for this class. So you should be quite familiar with this. This is to most extent, this is kind of more of a review for you. But basically this test data is, use it very sparingly, forget that you have it. Instead, what we do is we separate our training data into what we call folds. So we separate— say, we use a 5-fold validation. So we use 20% of the training data as an imagined test set data. And then we only train on part of it. And we test out the choices of hyperparameters on this validation set. So I'm going to train on my 4-folds and try out all the different Ks and all the different distance metrics and whatever else. If you're using approximate nearest neighbor, You have many other choices. You try it out, see what works best on that validation data. If you're feeling uncomfortable because you have very few training data points, people also sometimes use cross-validation, where you actually iterate the choice of your test or validation fold across these choices. So I'll first use 4, 1 to 4 for my training, and try out on 5, and then I cycle the choice of the validation fold across all the 5 choices. And I look at what works best across all the possible choices of my test fold fold, and then I just take whatever works best across all the possible scenarios. Okay? That's referred to as a cross-validation set— cross-validation. So in practice, the way this would look like, say we're cross-validating for K for a nearest neighbor classifier, is we are trying out different values of K, and this is our performance across 5 choices of the fold. So you can see that for every single K, we have 5 data points there. And then this is the accuracy, so high is good. and I'm plotting a line through the mean, and I'm also showing the bars for the standard deviations. So we see here is that the performance goes up on the— across these validation folds, um, as you go up, but at some point it starts to decay. So for this particular dataset, it seems that k 7 is the best choice. So that's what I'll use. I'll do this for all my hyperparameters, also for distance metric and so on. I do my cross-validation, I find the best hyperparameters, I set them, I fix them, then I evaluate a single time on the test set. Whatever number I get, that's what I report as an accuracy of a k-nearest neighbor classifier on this dataset. That's what goes into a paper, that's what goes into your final report, and so on. That's the final generalization result of what you've done. Okay. Any questions about this? Yep. [Speaker:AUDIENCE] So the reason that happens with k, is that because large k gives you high bias? I would be careful with that terminology, but basically it's about the statistics of the distribution of these data points in your label, in your data space. And so sometimes it's, it's basically hard to say, like you get— where is this picture? You see roughly what's happening is you get more clunkiness in more case, and it just depends on how clunky your dataset is. That's really what it comes down to, is how, how how blobby is it, or how specific is it. I know that's a very hand-wavy answer, but that's roughly what that comes down to. So different datasets will have different clunkiness. Yeah? How do we deal with skewed datasets? Skewed datasets. So what does that refer to? A lot more of one class than another class. So that's a technical question that I maybe don't want to get into right now, but we will address that later in the class probably. Oh yeah, go ahead. Shouldn't tuning hyperparameters dataset-specific be considered cheating? No, not at all, because your hyperparameters are just choices. You're not sure how to set them. And different datasets will require different choices, so you need to see what works best. In fact, when you try out different algorithms, because you're not sure what's going to work best on your data, the choice of your algorithm is also kind of like a hyperparameter. So you're just not sure what works. Different approaches will give you different generalization boundaries. They look different, and some datasets have different structure than others, so some things work better than others. You have to just train it, try it out. Okay, cool. I'd just like to point out that k-nearest neighbors is— no one basically uses this, so I'm just going through this just to get you used to this approach of really how this works with training, test splits, and so on. The reason this is never used is because first of all, it's very inefficient. But second of all, distance metrics on images, which are very high-dimensional objects, they act in very unnatural, unintuitive ways. So here what I've done is we're taking an original image, and I change it in 3 different ways. But all these 3 different images here have actually the exact same distance to this one in an L2 Euclidean sense. And so just think about it. This one here, is slightly shifted to the left. It's basically cropped slightly. And its distances here are completely different because these pixels are not matching up exactly, and it's all introducing all these errors, and you're getting a distance. This one is slightly darkened, so you get a small delta across all spatial locations. And this one is untouched, so you get zero distance errors across everywhere except for in those positions over there. And that is taking out critical pieces of the image, and it doesn't— the nearest neighbor classifier would not be able to really tell a difference between these settings. Because it's based on these distances that don't really work very well in this case. So very unintuitive things happen when you try to throw distances on very high-dimensional objects. That's partly why we don't use this. OK. So in summary so far, we're looking at image classification as a specific case. And we'll go into different settings later in the class. I've introduced the nearest neighbor classifier and the idea of having different splits of your data. And we have these hyperparameters that we need to pick. And we use cross-validation for this usually. Most of the time people don't actually use entire cross-validation. They just have a single validation set, and they try out on the validation set whatever works best in terms of the hyperparameters. And once you get the best hyperparameters, you evaluate a single time on a test set. Okay. So I'm going to go into linear classification in a bit. Any questions at this point? Otherwise, okay, great. Okay. So we're going to look at linear classification. This is the point where we are starting to work towards convolutional neural networks. So there will be a series of lectures. We'll start with linear classification. They will build up to an entire convolutional network analyzing an image. Now, I'd just like to say that we've motivated the class yesterday from a task-specific view. So this class is computer vision class. We're interested in, you know, giving machines sight. Another way to motivate this class would be from a model-based point of view. In the sense that we're giving you guys— we're teaching you guys about deep learning and neural networks. These are wonderful algorithms that you can apply to many different data domains, not just vision. So in particular, over the last few years, we saw that neural networks can not only see— that's what you'll learn a lot about in this class— but they can also hear. They're used quite a bit in speech recognition now. So when you talk to your phone, that's now a deep neural network. They can also do machine translation. So here you're feeding a neural network a set of words one by one in English, and the neural network produces the translation in French or whatever else target language you have. They can also perform control. So we've seen neural network applications in manipula— in robots manipulation, in playing of Atari games. So these neural networks learn how to play Atari games just by seeing the raw pixels of the screen. And we've seen neural networks be very successful in a variety of domains and even more than I put here, and we're uncertain exactly where this will take us. And then I'd like to also say that we're exploring ways for neural networks to think, but this is very hand-wavy, it's just wishful thinking. But there are some hints that maybe they can do that as well. Now, neural networks are very nice because they're just fun modular things to play with. When I think about working with neural networks, I kind of— this picture comes to mind for me. Here we have a neural networks practitioner, And she's building what looks to be a roughly 10-layer convolutional neural network at this point. [LAUGHTER] And so these are very fun. Really the best way to think about playing with neural networks is like Lego blocks. You'll see that we're building these little function pieces, these Lego blocks that we can stack together to create entire architectures. And they very easily talk to each other. And so we can just create these modules and stack them together and play with this very easily. One work that I think exemplifies this is my own work on image captioning from roughly a year ago. So here the task was you take an image and you're trying to get the neural network to produce a sentence description of the image. So for example, in the top left, these are test set results. The neural network would say that this is a man in black shirt is playing guitar, or a construction worker in orange safety vest is working on the road, and so on. So the neural network can look at the image and create this description of every single image. And when you go to the details of this model, the way this works is we're taking a Convolutional neural network, which we know— so there's two modules here in this system diagram for image captioning model. We're taking a convolutional neural network, which we know can see, and we're taking a recurrent neural network, which we know is very good at modeling sequences, in this case sequences of words that will be describing the image. And then just as if we were playing with Legos, we take those two pieces and we stick them together. That's corresponding to this arrow here in between the two modules. And these networks learn to talk to each other And in the process of trying to describe the images, these gradients will be flowing through the convolutional network, and the full system will be adjusting itself to better see the images in order to describe them at the end. And so this whole system will work, uh, together as one. Uh, so we'll be working towards this model. Uh, we'll actually cover this in class, so you'll have full understanding exactly of both this part and this part at about, uh, half— halfway through the course roughly. And you'll see how that image captioning model works. But that's just the motivation for really what we're building up to, and these are like really nice models to work with. Okay. But for now, back to, uh, CIFAR-10 and linear classification. Um, so again, just to remind you, we're working with this dataset, 50,000 images, 10 labels. And the way we're going to approach linear classification is from what we call a parametric approach. K-nearest neighbor that we just discussed now is something— an instance of what we call non-parametric approach. There's no parameters that we're going to be optimizing over. This distinction will become clear in, uh, few minutes. Uh, so in the parametric approach, what we're doing is we're thinking about constructing a function that takes an image and produces the scores for your classes, right? This is what we want to do. We want to take an image and we'd like to figure out which one of the 10 classes it is. So we'd like to write down a function, an expression that takes an image and gives you those 10 numbers. But the expression is not only a function of that image, but critically it will be also a function of these parameters that I'll call w. Sometimes also called the weights. And so really, it's a function that goes from 3,072 numbers, which make up this image, to 10 numbers. That's what we're doing. We're defining a function. And we'll go through several choices of this function. In this— in the first case, we'll look at linear functions, and then we'll extend that to get neural networks, and then we'll extend that to get convolutional neural networks. But intuitively, what we're building up to is that what we'd like is when we pipe this image through our function, We'd like the 10 numbers that correspond to the scores of the 10 classes. We'd like the number that corresponds to the cat class to be high and all the other numbers to be low. And we'll have— we don't have a choice over x. That x is our image that's given, but we'll have choice over w. So we'll be free to set this in whatever way we want, and we want— we'll want to set it so that this function gives us the correct answers for every single image in our training data. Okay, that's roughly the approach we're building up towards. So suppose that we use the simplest function, arguably the simplest, just a linear classification here. So x is our image. In this case, what I'm doing is I'm taking this array, this image that makes up the cat, and I'm stretching out all the pixels in that image into a giant column vector. So that x there is a column vector of 3,072 numbers. OK? And so in this case, if you know your matrix vector operations, which you should, that's a prerequisite for this class, that there is just a matrix multiplication, which you should be familiar with. And basically we're taking x, which is a 3,072-dimensional column vector. We're trying to get 10 numbers out, and it's a linear function. So you can go backwards and figure out that the dimensions of this W are basically 10 by 3,072. So there are 30,000— 3,700— numbers that goes into W. And that's what we have control over. That's what we have to tweak and find what works best on our data. So those are the parameters in this particular case. Uh, what I'm leaving out is there's also an appended plus b sometimes. So you have a bias. These biases are again 10 more parameters and, um, we have to also find those. So usually in a linear classifier you have a W and a b. We have to find exactly what works best. And this b is not a function of the image, that's just independent weights on the— on how likely any one of those images might be. So to go back to your question, if you have a very unbalanced dataset for— so maybe you have mostly cats but some dogs or something like that, then you might expect that the cat— the bias for the cat class might be slightly higher because by default the classifier wants to predict the cat class unless something convinces it otherwise. Something in the image would convince it otherwise. Okay? So to make this more concrete, uh, I just like to break it down, but of course I can't visualize it very explicitly with 3,072 numbers. So imagine that our input image only had 4 pixels, and imagine— so 4 pixels are stretched out in the column x, and imagine that we have 3 classes. So red, green, and blue class, or a cat, dog, ship class. Okay? So in this case, W will be only a 3 by 4 matrix, and what we're doing here is we're trying to compute the score of this, image X. So this is matrix multiplication going on here to give us the output of F, which is the scores. We got the 3 scores for 3 different classes. So this is a random setting of W, just random weights here, and we're carrying out the matrix multiplication to get some scores. So in particular, you can see that with this, this setting of W is not very good, right? Because with this setting of W, our cat score, -96, is much less than any of the other classes, right? So this was not correctly classified for this training image. So that's not— it's not a very good classifier. So we'd want to change a different— we'd want to use a different W so that that score comes out higher than the other ones. But we have to do that consistently across the entire training set of examples. But one thing to notice here as well is that basically W, it's— this function is in parallel evaluating all the 10 classifiers, but really there are 10 independent classifiers, uh, to some extent here. And every one of these classifiers, like say the cat classifier, is just the first row of W here, right? So the first row and the first bias gives you the cat score. And the dog classifier is the second row of W, and the ship score— the ship classifier, the third row of W. So basically this W matrix has all these different classifiers stacked in rows, and they're all being dot-producted with the image to give you the scores. OK? So here's a question for you. What does a linear classifier do in English? We saw the functional form. It's taking these images. It's doing this funny operation there. But how do we really interpret in English somehow what this is doing? What is this functional form really doing? Yeah, go ahead. [Speaker:AUDIENCE] If you just think of it as a single— Binary classifier, it's basically drawing a line that will tell you based on the observed observations in your data, if the point is below the line, then it's not this class. If it's above the line, then it's this class. And in higher dimensions, it's a hyperplane. OK, good. So you're thinking about it in a spatial domain of x being a high-dimensional data point, and w is really putting planes through this high-dimensional data point. I'll come back to that interpretation in a bit. What other way can we think about this? [Speaker:AUDIENCE] For each class that has like sort of a template image that it basically multiplies with every image, and whichever one comes through the brightest, that's the— [Speaker:ANDREJ KARPATHY] OK. So you're thinking about it more in kind of like a template-y way, where every single one of these rows of W effectively is like this template that we're dot producting with the image. And a dot product is really a way of like matching up, seeing what aligns. Good. What otherwise? Yep. I guess it's saying what he said but putting it in different words. It's just saying that this part of the image is an important attribute to be a cat. This part of the image is not an important part as an attribute to cat. Things like those kind of things. Mm-hmm. Yep. So what you're referring to is that W basically has the capacity to to care or not care about different spatial positions in the image, right? Because what we can do is some of the spatial positions in x, if we have zero weights, then the classifier would be— it doesn't care what's in part of the image. So if I have zero weights for this part here, then nothing affects it. But for some other parts of the image, if you have positive or negative weights, something's going to happen there, and this is going to contribute to the score. Any other ways of describing it? Yeah. Is this taking something that exists in image space and projecting it into a space of labels? Yeah. So it's taking— yeah, so you can think about it that also as a nice interpretation. It's like a mapping from image space to label space. Yeah. Good. How do you come up with each of the numbers in the column vector? Oh, I made that up. Sorry. How do you know the red, green, and blue values? Sorry? From the red, green, and blue values of each image? [Speaker:ANDREJ KARPATHY] Yeah, thank you. So good question. So this image is a 3-dimensional array where we have all these channels. You just stretch it out. So all the— you just stretch it out in whatever way you like. Say you stack the red, green, and blue portions side by side. That's one way. You just stretch it out in whatever way you like, but in a consistent way across all the images. You figure out a way to serialize in which way you want to read off the pixels, and you stretch them out into a column. So then when you have 12 values? For a 4-pixel image, yeah, OK, good point. OK, yeah. So let's say we have a 4-pixel grayscale image, which is— this is a terrible example. Thank you. You're right. Thank you. I didn't want to confuse people, especially because someone pointed out to me later after I made this figure that red, green, and blue are the color channels. But here the red, green, and blue correspond to classes. So this is a complete screw-up on my part. So I apologize. Not color channels, nothing to do with color channels, just 3 different colored classes. Sorry about that. OK, go ahead. So if we have a different size of the image, like 40 times 60, 100 times something like that, do you put a sort of zeros inside or delete a couple of index? Yeah, thank you. So your question is, what if my images have different sizes? In my dataset, some could be small, some could be large. Exactly how do we make this all be a single-sized column vector? The answer is we always resize images to be basically the same size. We can't easily deal with different-sized images. Or we can, and we might go into that later. But the simplest thing to think of is just resize every single image to the exact same size is the simplest thing. Because we want to ensure that all of them are kind of comparable of the same stuff so that we can make these columns and we can analyze statistical patterns that are aligned in the image space. Yeah. In fact, state-of-the-art methods, the way they actually work on this is they always work on square images. So if you have a very long image, these methods will actually work worse because many of them, what they do is just squash it. That's what we do. Still works fairly well. So yeah, if you have very long panorama images and you try to put that somewhere on some online service, chances are it might work worse because they'll probably, when they put it through a ConvNet, they will make it a square. Because these convnets always work on squares. You can make them work on anything, but that's just in practice what happens usually. Any other questions? Yeah? It's like assigning a score to each test image for each class. Yep. So you're interpreting the W, the classifier. Yeah. Yeah, so each image gets mapped through this setting. OK. Anyone else would like to interpret this? OK, great. Another way to actually put it, one way that I didn't hear but it's also a relatively nice way of looking at it, is that basically every single score is just a weighted sum of all the pixel values in the image. And these weights are— we get to choose those eventually. But it's just a giant weighted sum. It's really all it's doing is it's counting up colors, right? It's counting up colors at different spatial positions. So one way to— one way that was brought up in terms of how we can interpret this W classifier to make it concrete is that it's kind of like a bit like a template matching thing. So here what I've done is I trained a classifier, and I haven't shown you how to do that yet, but I trained my weight matrix W, and then I'll come back to this in a second. I'm taking out every single one of those rows that we've learned, every single classifier, and I'm reshaping it back to an image so that I can visualize it. Okay? So I'm taking it originally just a giant row of 3,072 numbers. I reshape it back to the image to undo the distortion I've done. And then I have all these templates. And so for example, what you see here is that plane is like a blue blob here. The reason you see blue blob is that if you looked at the color channels of this plane template, you'll see that in the blue channel, you'll have lots of positive weights because those positive weights, if they see blue values, then they interact with those and they get a little contribution to the score. So this plane classifier is really just counting up the amount of blue stuff in the image across all these spatial locations. And if you look at the red and the green channel for the plain classifier, you might find zero values or even negative values, right? So that's the plain classifier. And then we have classifiers for all these other images. So say a frog, you can almost see the template of the frog there, right? We're looking for some green stuffish— green stuff has positive weights in here. And then we see some brown stuffish things on the side, right? So if that gets put over an image and dot-producted, you'll get a high score. One thing to note here is that look at this, the car classifier, that's not a very like nice template of a car. Also here the horse looks a bit weird. What's up with that? Why is the car looking weird and why is the horse looking weird? Yeah. [Speaker:AUDIENCE] Some horses are facing left and some are facing right. We end up with this where it looks like a horse has two heads. [Speaker:ANDREJ KARPATHY] Yeah. Basically that's what's going on. In the data, the horses, some are facing left, some are right. And this classifier really is not a very powerful classifier. And it has to combine the two modes. It has to do both things at the same time. So you end up with this two-headed horse in there. And you can in fact say that just from this result, there's probably more left-facing horses in CIFAR than right, because it's stronger there. Also for car, right? We can have a car like 45 degrees tilted left or right or front. And this classifier here is the optimal way of mixing across, like merging all those modes into a single template, because that's what we're forcing it to do. Once we're actually doing ConvNets and neural networks, they don't have this downside. They can actually have— in principle, they can have a template for this car or that car or that car and combine across them. We're giving them more power to actually carry out this classification more properly. But for now, we're constrained by this. Question? If you only have one image of a horse or only a couple, could you rotate it yourself much different ways and skew it in certain ways so that the classifier wouldn't overtrain to one —orientation? Yes, what you're referring to, I think, is something we call data augmentation. So at training time, we would not be taking just the exact images, but we'll be jittering them, stretching them, skewing them, and we'll be piping all of that in. That's going to become a huge part of getting ConvNets to work very well. So yeah, so we'll be doing a huge amount of that stuff. For every single training example, we're going to hallucinate many other training examples of shifts and rotates and skews, and that works much better. Go ahead. [Speaker:AUDIENCE] How do these templates differ from just taking the average pixel value for each class? [Speaker:ANDREJ KARPATHY] How do these templates change— taking the average pixel value? [Speaker:AUDIENCE] Like all the images for a plane, and it took the average of all the images. [Speaker:ANDREJ KARPATHY] I see. So you want to explicitly set a template. And the way you'll set the template is you'll take the average across all the images, and that becomes your template? Sure. I was just wondering— Yeah. —how those two approaches would differ. So this classifier, it finds— it would do something similar. I would guess it would work worse because the linear classifier, when you look at its mathematical form and really what it optimizes for, I don't think it would have a minimum at what you described in just the mean of the images. But that would be like an intuitively decent heuristic to perhaps set the weights in the initialization or something like that. [Speaker:AUDIENCE] Is there a classifier that does that, like Fisher or something? [Speaker:ANDREJ KARPATHY] Yeah, there's something related to it. Yeah. Yeah, but we might even go into that. LDA probably is what you're referring to. There's several things. OK? Yeah? [Speaker:AUDIENCE] Don't you think it would be much better if we do it with grayscale images? Because let's say we got a car that was yellowish, right? —right? But our template image highlights red. Right. So wouldn't it be better if we use grayscale? Yeah, so that's a good point. So there are— cars have many different colors. And here, this happened to pick up on red, which is saying that there's probably more red cars in the dataset. And it might not work for yellow. In fact, yellow cars might be frog for this classifier, right? So this thing just does not have capacity to do all of that, which is why it's not powerful enough. It can't capture all these different modes correctly. And so this will just go after the numbers. There's more red cars, that's where it will go. Uh, if this was grayscale, I'm not sure if that would work better. I'll come back to that actually in a bit. Go ahead. If you have a training set with more examples for cat, would that affect the bias higher? And if so, would that affect the test? Uh, yeah. So you might expect, as I mentioned, for unbalanced datasets, what you might expect, um, not exactly. What you might expect if you have lots of cats is that the cat bias would be higher because this classifier is just used to spewing out large numbers based on the loss. But we have to go into the loss function to exactly see how that will play out. So it's hard to say right now. Okay. Another interpretation of the linear classifier that also someone else pointed out that I'd like to point out is you can think of these images as very high-dimensional points. In a 3,072-dimensional space, right? In the 3,072-pixel space— dimensional pixel space, every image is a point, and these linear classifiers are describing these gradients across the 3,072-dimensional space. These scores are this gradient of negative to positive along some linear direction across the space. And so for example, here for a car classifier, I'm taking the first row of W, which is the car class, and the line here is indicating the zero-level set of that classifier. Classifier. In other words, that— along that line, the car classifier has zero score. So the car classifier there has zero, and then the arrow is indicating the direction along which it will color the space, uh, with more and more car-ness of score. Similar, we have these three different classifiers in this example. They will all correspond to these gradients with a particular level set, and they're basically trying to go in. You have all these points, they are in this space, and these linear classifiers, we initialize them randomly. So this car classifier would have its level set at random. And then you'll see when we actually do the optimization, as we optimize, this will start to shift, turn, and it will try to isolate the car class. And it will, like— it's really fun to watch these classifiers train because it will rotate. It will snap in for the car class, and it'll start to jiggle. And it will try to separate out all the cars from all the non-cars. It's really amusing to watch. So that's another way of interpreting that someone has brought up. Okay. So here's a question for you given all these interpretations. What would be a very hard test set given how the linear classifier works? What would you expect to work really— just really not well with a linear classifier? Concurrent circles. Sorry? Concurrent circles. Concurrent circles. So your classes are— What are your classes exactly? So you have a red class in the middle that's like circle or like a blob of red classes. And then around it, you have a blob of blue classes. Oh, I see. So you're in— OK. So what you're describing is in this interpretation of space, if your images in one class would be in a blob and then your other class is like around it. So I'm not sure exactly what that would look like if you actually visualize it in a pixel space. But yes, you're right. In that case, linear classifier would not be able to separate out those. But what about in terms of like, what would the images look like? You would look at this data set of images and you clearly say that linear classifier will probably not do very well here. Yeah, go ahead. [Speaker:AUDIENCE] You want to separate like scooters from motorcycles basically or something like that. Because I think somebody else was asking about the averaging of the pictures. And that made me think, if you're doing like ordinary least squares, what you're basically doing is maximizing projections of all of the axes onto your row space. So if you look at training axes of scooters and training axes of motorcycles, they're going to effectively yield the same centroid for the template. And then you're going to get the same situation you were describing where you have concentric circles in your high-dimensional space. Mm-hmm. Yep, yep. So that's a pretty good one. Yeah, go ahead. Maybe the negative images, like Shane You know, subtracting 255, whatever the color is, you know, like— So you want one class to be, say, you take all the airplanes and then you want to switch— Yeah, it's kind of like an airplane to a human if it were the negative, like film negative image of a— Oh, I see. It would be actually the lowest scoring. Oh, I see, I see. So you're pointing out that if I took that image of an airplane class and I have a trained classifier and then I do a negative of it, negative image of that classifier, you'd still see the edges and you'll say, okay, that's an airplane obviously by the shape. But for a linear classifier, all the colors would be exactly wrong. And so the linear classifier would hate that airplane. So yeah, good example. Go ahead. [Speaker:AUDIENCE] If you take the same exact image and you translate it or scale it differently and you move it to different places or rotate it for each class, you have several of these, I would expect that to perform poorly. [Speaker:ANDREJ KARPATHY] I see. So you're saying that we take one thing, say like dogs, but then So what you're referring to is say you have dogs. One class is dogs in the center and one class is dogs on the right. And you think that that would be a— Yeah, I'm saying even if it's a picture of the same exact dog, same pose and everything, you just move it to the right, up, down, or you scale it to different sizes and move it around within it. So would that be a problem if— so one class is dogs in the center and one class is dogs on the right, but otherwise white background or something like that. Would that be a problem? It wouldn't be a problem? Why wouldn't it be a problem? Because it's an affine transformation. It's an affine transformation? It's a linear transformation when you are modeling. I guess that the problem would be if you warp an image. You have a set of images like the dogs and dogs warped or skewed in some nonlinear way. I see. Difficult for a classifier. Right, so you're saying that maybe a more difficult thing would be if you have dogs that are warped in some funny ways according to a class. Why wouldn't it be a problem if you actually Could a linear classifier do something in the center and something on the right? Does it actually have an understanding of spatial layout? It'd actually be fine, right? That would be relatively easy because you would have positive weights in the middle. Oh, sorry. Oh, sorry. Okay, maybe I misunderstood. I'm sorry. Okay, another one. Would classifying different types of paintings with the author be hard because they use a bunch of different colors and a bunch of different styles? Uh, yeah, possibly. Yeah. So I think many of you are kind of understanding the main point is, uh, Yeah, so this is really, really what it's doing. Well, I'm skipping ahead here. Really what this is doing is it's counting up colors in spatial positions. Anything that messes with this will be really hard. Actually, to go back to your point, if you had a grayscale dataset, by the way, that would work not very well. Linear classifiers would probably not work. If you took CIFAR-10 and you made it all grayscale, then doing the exact CIFAR-10 classification but on grayscale images would probably work really terribly. Because you can't pick up on the colors. You have to pick up on these textures and fine details now, and you just can't localize them because they could be at arbitrary positions. You can't consistently count across it. So yeah, that would be kind of a disaster. Another example would be different textures. If you have, say, all of your textures are blue, but these textures could be different types, then this doesn't really— like, say these textures could be different types, but they can be spatially invariant, then that would be terrible. Terrible for a linear classifier as well. Okay, good. Uh, so just to remind you, I think, uh, nearly there. Um, we defined this linear function. So with a specific case of W, we're looking at some test images, we're getting some scores out. And just looking forward where we're headed now is with some setting of Ws, we're getting some scores for all these images. And so for example, with this setting of W in this image, we're seeing that the cat score is 2.9, But there are some classes that got a higher score like dog, so that's not very good, right? But some classes have negative scores which is, uh, good for this image. So this is a kind of a medium result for this weights for this image. And here we see that the car class which is correct for there has the highest score which is good, right? So this setting of W worked well on this image. Here we see that the frog class is a very low score, so W works terribly on that image. So where we're headed now, is we're going to define what we call a loss function. And this loss function will quantify this intuition of what we consider good or bad. Right now we're just eyeballing these numbers and saying what's good, what's bad. We have to actually write down a mathematical expression that tells us exactly, like, this setting of W across our test set is 12.5 bad, or 12 point whatever bad, or 1.0 bad. Because then once we have it defined specifically, we're going to be looking for Ws that minimize the loss. and it will be set up in such a way that when you have a loss of very low numbers, like say even 0, then you're correctly classifying all your images. But if you have a very high loss, then everything is messed up and W is not good at all. So we're going to define a loss function, and then we're going to look for different Ws that actually do very well across all of it. So that's roughly what's coming up. We'll define loss function, which is a quantify— a way to quantify how how bad each W is on our dataset. The loss function is a function of your entire training set and your weights. We don't have, um, control over the training set, but we have control over the weights. Then we're going to look at the process of optimization. How do we efficiently find the set of weights W that works across all the images and gives us a very low loss? And then eventually what we'll do is we'll go back and we'll look at this expression, the linear classifier that we saw, and we're going to start meddling with the function f here. So we're going to extend f to not be that simple linear expression, but we're going to make it slightly more complex. We'll get a neural network out. And then we'll make it slightly more complex, and we'll get a convolutional network out. But otherwise, the entire framework will stay unchanged. All the time, we'll be computing these scores. This functional form will be changing, but we're going from image to some set of scores through some function. And we'll make it more elaborate over time. And then we're identifying some loss function, and we're looking at what weights, what parameters are giving us very low loss. And that's the setup we'll be working with going forward. So next class, we'll look into loss functions, and then we'll go towards neural networks and ConvNets. So I guess this is my last slide, so I can take any last questions. And then— yeah? Can you explain the advantage of this heteronym approach over, say, just running on just 0, 1 linear regression? Sorry, sorry. Wait, sorry, I didn't hear. So I was saying, why are we doing this iterative approach instead of just say doing a minus 0 to 1 linear regression? There was nothing— Why are we doing iterative approach in the optimization? Right. So sometimes in optimization settings, you can have— these iterative approaches are basically the way this will work. We'll always start off with a random W. So that will give us some loss. And then we don't have a process of finding right away the best set of weights. What we do have a process for is iteratively slightly improving the weights. So what we'll see is we'll look at the loss function and we'll find the gradient in the parameter space, and we'll march down. So what we do know how to do is how do we slightly improve a set of weights. We don't know how to do the problem of just find the best set of weights right away. We don't know how to do that. Because especially when these functions are very complex, like say entire ConvNets, it's a huge landscape of— it's just a very intractable problem. Is that your question? I'm not sure. OK, thank you. Yep? How do you deal with that color problem? How do we deal with the color problem? Yeah. Since we had a high bias of red cars. Oh, so OK, so here we saw that the linear classifier for car was this red template for a car. A neural network, basically what we'll do is we'll be— you can look at it as stacking linear classifiers. To some degree. So what it will end up doing is it will have all these little templates, really, for red cars, yellow cars, green cars, whatever cars going this way or that way or that way. There will be a neuron assigned to detecting every one of these different modes, and then they will be combined across them on the second layer. So basically you'll have these neurons looking for different types of cars, and then the next neuron will be just like, okay, I just take a weight at some of you guys and I'm just doing an OR operation over you, and then we can detect cars in all of their modes and all of their positions, if that makes sense. So that's roughly how it will work. Make sense? OK, awesome.