AI 534 Machine Learning HW1a: $k$-NN for Image Classification (weeks 0-1)

Due Monday of Week 2 (11:59pm) on Canvas

Instructions:

1. The point of this HW is to get you used to numpy, sklearn, and basic broadcasting.
2. You can do this HW either on Google Colab or your own machine (if you install Anaconda -- choose Anaconda NOT miniconda, so that numpy, sklearn and other packages are automatically installed).
3. You need to submit (a) your notebook (.ipynb) AND (b) a PDF version of your notebook (.pdf) on Canvas. From your notebook you can save it as PDF (File -> Save and Export as -> PDF).
4. Please read official numpy tutorial and broadcasting tutorial.

Part 0: Data Preparation and "Average" Digits

import numpy as np
from sklearn.datasets import fetch_openml
import matplotlib.pyplot as plt # for plotting

# Download MNIST dataset from OpenML as NumPy arrays
X, y = fetch_openml('mnist_784', version=1, return_X_y=True, as_frame=False, parser='auto')

# Ensure types are correct (labels as integers)
y = y.astype(np.int64) # convert labels from str to int

print("Data shape (X):", X.shape)     # (70000, 784) each image is a 784-dimensional vector (28x28 grayscale pixels)
print("Labels shape (y):", y.shape) # (70000,) each label is an integer 0...9

Data shape (X): (70000, 784)
Labels shape (y): (70000,)

plt.imshow(X[0].reshape(28, 28)) # should show a "5"

<matplotlib.image.AxesImage at 0x1686f2120>

y[0] # 5

np.int64(5)

Question: how to show the "average" image from all images of label 0? Hint: use boolean masking y == 0.

Please write some simple code to show the "average" image for each digit from 0 to 9.

Note that besides the top-level for-loop (i=0..9), no more for-loop is allowed. The point of this exercise is to get you used to numpy's indexing and masking. You can use np.mean(axis=...).

FYI The following image is the average 0 in MNIST (i.e., mean over all images of digits 0).

for i in range(10): # 10 classes: 0...9
    # your code for computing and plotting average image i
    # no more for-loop is allowed!
    ...
    plt.show() # you have to show() each image, otherwise only the last one shows

Part 1: Use sklearn's k-NN

Use sklearn's $k$-NN classifier (see below) to write a function that performs $k$-NN classification on X_dev and report error rate (with y_dev), using X_train and y_train as the training data.

from sklearn.neighbors import KNeighborsClassifier

def sklearn_kNN(X_train, y_train, X_dev, y_dev, k=1):
    # return error rate as a float between 0 and 1
    # your code here

# test your code on 1-NN using 1,000 training examples and 100 test examples
print(sklearn_kNN(X[:1000], y[:1000], X[5000:5100], y[5000:5100], 1)) # should print 0.13

# you should do more testing here, such as varying k and varying training/dev sizes (e.g., 5,000 or 1,0000 training examples)
# make sure training and dev do not overlap! (otherwise it's cheating!)

Part 2: Implement your own 1-NN, the loop + simple broadcasting way

Now you need to implement your own 1-NN using numpy.

The high-level idea is for each test (or dev) example q (a 784-dimensional vector),

1. subtract it from all training examples; you should do this by broadcasting (matrix - vector) instead of writing another for-loop. Now you have a matrix of shape (1000, 784) (assuming 1000 training examples) that represent the difference vectors x-q for each training example x.
2. compute the distances (i.e., $\ell_2$-norms) so that you can 1000 distances.
3. get the training index for the smallest distance (use np.argmin()).
4. get the training label for that index.

You're only allowed to use one for-loop in this process (i.e., for each test/dev example).

To start with, first implement 1-NN using

Then extend it to $k$-NN using np.argpartition() or np.argsort().

# your 1-NN
def my_1NN(X_train, y_train, X_dev, y_dev):
    # return error rate

# verify your 1-NN
print(my_1NN(X[:1000], y[:1000], X[5000:5100], y[5000:5100])) # should print 0.13

Part 3: Implement your own k-NN

Now extend your work to $k$-NN using np.argpartition() or np.argsort().

Change the last two steps to:

3. get the training indices for the $k$ smallest distance (use np.argsort() or np.argpartition()).
4. get the training labels for those $k$ indices and take a majority vote.

# your k-NN
def my_kNN(X_train, y_train, X_dev, y_dev, k=1):
    # return error rate

# verify your k-NN with your sklearn_kNN by testing at least 3 cases

Part 4: (Optional, Extra Credit) Advanced Broadcasting

It turns out you can even remove the only for-loop by advanced broadcasting, so that you can all pairwise difference vectors or even directly pairwise distances between training examples and test/dev examples. Compare your result with your work above and make sure they get the same error rates. Is your new method faster?

Hint: there are two possible methods here:

1. one very slow with large data (using 3D tensors) and
2. one extremely fast (using matrix multiplication).