Great chart!

Datasets

• CIFAR-10 has 10 classes and 60,000 32 X 32 images

Nearest Neighbor Classifier

1. take a test image

2. go through every one of the training images, and predict the one that is closest (you do this by taking the absolute pixel distance)

You can use either L1 or L2 norm; these have theoretical foundations, but just keep in mind that L2 is less forgiving for larger distances.

K Nearest Neighbor Classifier

1. take a test image

2. Find the $k$ closest image by distance, and have it vote on the test image class

Here’s a toy example. See how the ensemble method is usually better!

Tips and tricks

1. preprocess data, using normalization

2. reduce dimensionality if needed

3. use approximate nearest neighbor if exact nearest neighbor is taking too long

4. L1 (coordinate, or Manhattan) and L2 distances will influence how KNN behaves. In general, L1 is sensitive to how the axes are oriented, while the L2 is not.

What’s the problem?

The problem is this: L1 or L2 pixel distance doesn’t correspond to the semantic content of the image at all! For example, backgrounds will have a large impact on the image distance, which is a spurious correlation. We need a smarter approach.

Validation

Use a validation set to tune your hyperparmaeters. Cross-validation happens if you use multiple validation splits to get a more reliable result.