Untitled
unknown
plain_text
10 days 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