Untitled
unknown
plain_text
a month ago
19 kB
4
Indexable
"""
Implements a K-Nearest Neighbor classifier in PyTorch.
"""
import torch
from typing import Dict, List
def hello():
"""
This is a sample function that we will try to import and run to ensure that
our environment is correctly set up on Google Colab.
"""
print("Hello from knn.py!")
def compute_distances_two_loops(x_train: torch.Tensor, x_test: torch.Tensor):
"""
Computes the squared Euclidean distance between each element of training
set and each element of test set. Images should be flattened and treated
as vectors.
This implementation uses a naive set of nested loops over the training and
test data.
The input data may have any number of dimensions -- for example this
function should be able to compute nearest neighbor between vectors, in
which case the inputs will have shape (num_{train, test}, D); it should
also be able to compute nearest neighbors between images, where the inputs
will have shape (num_{train, test}, C, H, W). More generally, the inputs
will have shape (num_{train, test}, D1, D2, ..., Dn); you should flatten
each element of shape (D1, D2, ..., Dn) into a vector of shape
(D1 * D2 * ... * Dn) before computing distances.
The input tensors should not be modified.
NOTE: Your implementation may not use `torch.norm`, `torch.dist`,
`torch.cdist`, or their instance method variants (`x.norm`, `x.dist`,
`x.cdist`, etc.). You may not use any functions from `torch.nn` or
`torch.nn.functional` modules.
Args:
x_train: Tensor of shape (num_train, D1, D2, ...)
x_test: Tensor of shape (num_test, D1, D2, ...)
Returns:
dists: Tensor of shape (num_train, num_test) where dists[i, j]
is the squared Euclidean distance between the i-th training point
and the j-th test point. It should have the same dtype as x_train.
"""
# Initialize dists to be a tensor of shape (num_train, num_test) with the
# same datatype and device as x_train
num_train = x_train.shape[0]
num_test = x_test.shape[0]
dists = x_train.new_zeros(num_train, num_test)
##########################################################################
# TODO: Implement this function using a pair of nested loops over the #
# training data and the test data. #
# #
# You may not use torch.norm (or its instance method variant), nor any #
# functions from torch.nn or torch.nn.functional. #
##########################################################################
# Replace "pass" statement with your code
# flattening data matrices
x_train = x_train.reshape(num_train, -1)
x_test = x_test.reshape(num_test, -1)
for i in range(num_train):
for j in range(num_test):
vec_1 = x_train[i]
vec_2 = x_test[j]
dists[i][j] = ((vec_1 - vec_2) ** 2).sum()
##########################################################################
# END OF YOUR CODE #
##########################################################################
return dists
def compute_distances_one_loop(x_train: torch.Tensor, x_test: torch.Tensor):
"""
Computes the squared Euclidean distance between each element of training
set and each element of test set. Images should be flattened and treated
as vectors.
This implementation uses only a single loop over the training data.
Similar to `compute_distances_two_loops`, this should be able to handle
inputs with any number of dimensions. The inputs should not be modified.
NOTE: Your implementation may not use `torch.norm`, `torch.dist`,
`torch.cdist`, or their instance method variants (`x.norm`, `x.dist`,
`x.cdist`, etc.). You may not use any functions from `torch.nn` or
`torch.nn.functional` modules.
Args:
x_train: Tensor of shape (num_train, D1, D2, ...)
x_test: Tensor of shape (num_test, D1, D2, ...)
Returns:
dists: Tensor of shape (num_train, num_test) where dists[i, j]
is the squared Euclidean distance between the i-th training point
and the j-th test point. It should have the same dtype as x_train.
"""
# Initialize dists to be a tensor of shape (num_train, num_test) with the
# same datatype and device as x_train
num_train = x_train.shape[0]
num_test = x_test.shape[0]
dists = x_train.new_zeros(num_train, num_test)
##########################################################################
# TODO: Implement this function using only a single loop over x_train. #
# #
# You may not use torch.norm (or its instance method variant), nor any #
# functions from torch.nn or torch.nn.functional. #
##########################################################################
# Replace "pass" statement with your code
# flattening data matrices
x_train = x_train.reshape(num_train, -1)
x_test = x_test.reshape(num_test, -1)
for i in range(num_train):
vec_1 = x_train[i]
squared_distances = ((x_test - vec_1) ** 2).sum(dim=1)
dists[i] = squared_distances
##########################################################################
# END OF YOUR CODE #
##########################################################################
return dists
def compute_distances_no_loops(x_train: torch.Tensor, x_test: torch.Tensor):
"""
Computes the squared Euclidean distance between each element of training
set and each element of test set. Images should be flattened and treated
as vectors.
This implementation should not use any Python loops. For memory-efficiency,
it also should not create any large intermediate tensors; in particular you
should not create any intermediate tensors with O(num_train * num_test)
elements.
Similar to `compute_distances_two_loops`, this should be able to handle
inputs with any number of dimensions. The inputs should not be modified.
NOTE: Your implementation may not use `torch.norm`, `torch.dist`,
`torch.cdist`, or their instance method variants (`x.norm`, `x.dist`,
`x.cdist`, etc.). You may not use any functions from `torch.nn` or
`torch.nn.functional` modules.
Args:
x_train: Tensor of shape (num_train, C, H, W)
x_test: Tensor of shape (num_test, C, H, W)
Returns:
dists: Tensor of shape (num_train, num_test) where dists[i, j] is
the squared Euclidean distance between the i-th training point and
the j-th test point.
"""
# Initialize dists to be a tensor of shape (num_train, num_test) with the
# same datatype and device as x_train
num_train = x_train.shape[0]
num_test = x_test.shape[0]
dists = x_train.new_zeros(num_train, num_test)
##########################################################################
# TODO: Implement this function without using any explicit loops and #
# without creating any intermediate tensors with O(num_train * num_test) #
# elements. #
# #
# You may not use torch.norm (or its instance method variant), nor any #
# functions from torch.nn or torch.nn.functional. #
# #
# HINT: Try to formulate the Euclidean distance using two broadcast sums #
# and a matrix multiply. #
##########################################################################
# Replace "pass" statement with your code
# flattening data matrices
x_train = x_train.reshape(num_train, -1)
x_test = x_test.reshape(num_test, -1)
# Compute squared norms
x_test_squared = (x_test ** 2).sum(dim=1).unsqueeze(0)
x_train_squared = (x_train ** 2).sum(dim=1).unsqueeze(1)
# Compute inner product
cross_term = x_train @ x_test.T
# Apply the formula
dists = x_test_squared + x_train_squared - 2 * cross_term
##########################################################################
# END OF YOUR CODE #
##########################################################################
return dists
def predict_labels(dists: torch.Tensor, y_train: torch.Tensor, k: int = 1):
"""
Given distances between all pairs of training and test samples, predict a
label for each test sample by taking a MAJORITY VOTE among its `k` nearest
neighbors in the training set.
In the event of a tie, this function SHOULD return the smallest label. For
example, if k=5 and the 5 nearest neighbors to a test example have labels
[1, 2, 1, 2, 3] then there is a tie between 1 and 2 (each have 2 votes),
so we should return 1 since it is the smallest label.
This function should not modify any of its inputs.
Args:
dists: Tensor of shape (num_train, num_test) where dists[i, j] is the
squared Euclidean distance between the i-th training point and the
j-th test point.
y_train: Tensor of shape (num_train,) giving labels for all training
samples. Each label is an integer in the range [0, num_classes - 1]
k: The number of nearest neighbors to use for classification.
Returns:
y_pred: int64 Tensor of shape (num_test,) giving predicted labels for
the test data, where y_pred[j] is the predicted label for the j-th
test example. Each label should be an integer in the range
[0, num_classes - 1].
"""
num_train, num_test = dists.shape
y_pred = torch.zeros(num_test, dtype=torch.int64)
##########################################################################
# TODO: Implement this function. You may use an explicit loop over the #
# test samples. #
# #
# HINT: Look up the function torch.topk #
##########################################################################
# Replace "pass" statement with your code
for j in range(num_test):
# Get distances to the j-th test sample
distances = dists[:, j]
# Find indices of k smallest distances
_, topk_indices = torch.topk(distances, k=k, largest=False)
# Get labels of these k nearest neighbors
topk_labels = y_train[topk_indices]
# Count frequency of each label
label_counts = torch.bincount(topk_labels, minlength=y_train.max().item() + 1)
# Pick label with highest count (break ties by choosing the smallest label)
y_pred[j] = torch.argmax(label_counts)
##########################################################################
# END OF YOUR CODE #
##########################################################################
return y_pred
class KnnClassifier:
def __init__(self, x_train: torch.Tensor, y_train: torch.Tensor):
"""
Create a new K-Nearest Neighbor classifier with the specified training
data. In the initializer we simply memorize the provided training data.
Args:
x_train: Tensor of shape (num_train, C, H, W) giving training data
y_train: int64 Tensor of shape (num_train, ) giving training labels
"""
######################################################################
# TODO: Implement the initializer for this class. It should perform #
# no computation and simply memorize the training data in #
# `self.x_train` and `self.y_train`, accordingly. #
######################################################################
# Replace "pass" statement with your code
self.x_train = x_train
self.y_train = y_train
######################################################################
# END OF YOUR CODE #
######################################################################
def predict(self, x_test: torch.Tensor, k: int = 1):
"""
Make predictions using the classifier.
Args:
x_test: Tensor of shape (num_test, C, H, W) giving test samples.
k: The number of neighbors to use for predictions.
Returns:
y_test_pred: Tensor of shape (num_test,) giving predicted labels
for the test samples.
"""
y_test_pred = None
######################################################################
# TODO: Implement this method. You should use the functions you #
# wrote above for computing distances (use the no-loop variant) and #
# to predict output labels. #
######################################################################
# Replace "pass" statement with your code
num_test = x_test.shape[0]
x_test = x_test.reshape(num_test, -1)
dists = compute_distances_no_loops(self.x_train, x_test)
y_test_pred = predict_labels(dists, self.y_train, k=k)
######################################################################
# END OF YOUR CODE #
######################################################################
return y_test_pred
def check_accuracy(
self,
x_test: torch.Tensor,
y_test: torch.Tensor,
k: int = 1,
quiet: bool = False
):
"""
Utility method for checking the accuracy of this classifier on test
data. Returns the accuracy of the classifier on the test data, and
also prints a message giving the accuracy.
Args:
x_test: Tensor of shape (num_test, C, H, W) giving test samples.
y_test: int64 Tensor of shape (num_test,) giving test labels.
k: The number of neighbors to use for prediction.
quiet: If True, don't print a message.
Returns:
accuracy: Accuracy of this classifier on the test data, as a
percent. Python float in the range [0, 100]
"""
y_test_pred = self.predict(x_test, k=k)
num_samples = x_test.shape[0]
num_correct = (y_test == y_test_pred).sum().item()
accuracy = 100.0 * num_correct / num_samples
msg = (
f"Got {num_correct} / {num_samples} correct; "
f"accuracy is {accuracy:.2f}%"
)
if not quiet:
print(msg)
return accuracy
def knn_cross_validate(
x_train: torch.Tensor,
y_train: torch.Tensor,
num_folds: int = 5,
k_choices: List[int] = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100],
):
"""
Perform cross-validation for `KnnClassifier`.
Args:
x_train: Tensor of shape (num_train, C, H, W) giving all training data.
y_train: int64 Tensor of shape (num_train,) giving labels for training
data.
num_folds: Integer giving the number of folds to use.
k_choices: List of integers giving the values of k to try.
Returns:
k_to_accuracies: Dictionary mapping values of k to lists, where
k_to_accuracies[k][i] is the accuracy on the i-th fold of a
`KnnClassifier` that uses k nearest neighbors.
"""
# Split data into folds
x_train_folds = torch.chunk(x_train, num_folds)
y_train_folds = torch.chunk(y_train, num_folds)
k_to_accuracies: Dict[int, List[float]] = {}
for k in k_choices:
k_to_accuracies[k] = []
for i in range(num_folds):
# Prepare validation fold
x_val = x_train_folds[i]
y_val = y_train_folds[i]
# Prepare training folds (all but i)
x_train_fold = torch.cat([x_train_folds[j] for j in range(num_folds) if j != i], dim=0)
y_train_fold = torch.cat([y_train_folds[j] for j in range(num_folds) if j != i], dim=0)
# Create classifier and evaluate
classifier = KnnClassifier(x_train_fold, y_train_fold)
acc = classifier.check_accuracy(x_val, y_val, k=k, quiet=True)
# Store accuracy
k_to_accuracies[k].append(acc)
return k_to_accuracies
def knn_get_best_k(k_to_accuracies: Dict[int, List]):
"""
Select the best value for k, from the cross-validation result from
knn_cross_validate. If there are multiple k's available, then you SHOULD
choose the smallest k among all possible answer.
Args:
k_to_accuracies: Dictionary mapping values of k to lists, where
k_to_accuracies[k][i] is the accuracy on the i-th fold of a
`KnnClassifier` that uses k nearest neighbors.
Returns:
best_k: best (and smallest if there is a conflict) k value based on
the k_to_accuracies info.
"""
best_k = None
best_mean_accuracy = -1 # Initialize to a value that will be lower than any possible accuracy
for k, accuracies in k_to_accuracies.items():
# Calculate the mean accuracy for this value of k
mean_accuracy = sum(accuracies) / len(accuracies)
# Update best_k if we find a higher mean accuracy or a tie with a smaller k
if mean_accuracy > best_mean_accuracy or (mean_accuracy == best_mean_accuracy and (best_k is None or k < best_k)):
best_k = k
best_mean_accuracy = mean_accuracy
return best_k
Editor is loading...
Leave a Comment