[cs231n_review#Lecture 2-2] Nearest Neighbor classifier

 

you might imagine working on this dataset called CIFAR-10, which is very commonly used in machine learning, as kind of a small test case. the CIFAR-10 dataset gives you 10 different classes, and for each of those 10 categories it provides 50,000 training images, roughly evenly distributed across these 10 categories. And then 10,000 additional testing images that you're supposed to test your algorithm on.

So here's an example of applying this simple nearest neighbor classifier to some of these test images on CIFAR-10.

 

So, if we're applying the nearest neighbor algorithm to this image, we'll find the closest example in the training set. You can see from these examples that is probably not but it's still kind of a nice example to work through.

 

-> how can we actually compare them?

we actually have many different choices for exactly what that comparison function should look like.

so, we've used what's called the L1 distance, also sometimes called the Manhattan distance.

And that's that we're going to just compare individual pixelsin these images.

 

So, supposing that our test image is maybe just a tiny four by four image of pixel values, then we're take this upper-left hand pixel of the test image, subtract off the value in the training image, take the absolute value, and get the difference in that pixel between the two images. And then, sum all these up across all the pixels in the image.

 

So now, a couple questions about this simple classifier.

Q. First, if we have NN-classifier examples in our training set, then how fast can we expect training and testing to be?

A,  Well, training is probably constant O(1). and prediction has O(n).

 

but, you really want the testing time performance of your classifier to be quite fast. So, from this perspective, this nearest neighbor algorithm, is, actually, a little bit backwards.

 

convolutional neural networks, and other types of parametric models, they'll be the reverse of this. Where you'll spend a lot of compute at training time, but then they'll be quite fast at testing time.

 

 

So then, the question is,

Q. what exactly does this nearest neighbor algorithm look like when you apply it in practice?

So, here we've drawn, what we call the decision regions

the color of the point represents the category, or the class label, of that point.

generally when you're using nearest neighbors classifiers, you almost always want to use some value of K, which is larger than one because this tends to smooth out your decision boundaries and lead to better results.

k-nearest neighbors algorithm(k-NN) is a non-parametric supervised learning method. It is also called a lazy learner algorithm because it does not learn from the training set immediately instead it stores the dataset and at the time of classification, it performs an action on the dataset.

The K-NN working can be explained on the basis of the below algorithm:
Step-1: Select the number K of the neighbors
Step-2: Calculate the Euclidean distance of K number of neighbors
Step-3: Take the K nearest neighbors as per the calculated Euclidean distance.
Step-4: Among these k neighbors, count the number of the data points in each category.
Step-5: Assign the new data points to that category for which the number of the neighbor is maximum.
Step-6: Our model is ready.

https://www.javatpoint.com/k-nearest-neighbor-algorithm-for-machine-learning

what is the deal with these white regions? The white regions are where there was no majority among the k-nearest neighbors. for this simple example we're just coloring it white to indicate there was no nearest neighbor in those points.

 

So, these choices, of things like K and the distance metric, we call hyperparameters, because they are not necessarily learned from the training data, instead these are choices about your algorithm that you make ahead of time and there's no way to learn them directly from the data.