Vectorized 1-Nearest Neighbor with a Manhattan Option
Problem statement
You are given a labeled training set and a batch of query points, all as integer feature vectors. Build a 1-nearest-neighbor classifier in numpy: each query gets the label of the closest training point.
def nn1_predict(X_train: list, y_train: list, X_query: list, metric: str) -> list:
# X_train: n x d ints, y_train: n int labels, X_query: m x d ints
# metric: 'euclidean' or 'manhattan'
# returns: m labels (ints)
...
Part 1: Euclidean, vectorized. For metric = 'euclidean', compute all query-to-training distances with numpy array operations (no Python loop over individual queries, training points or pairs; looping over chunks of queries is fine). When several training points are exactly equally close to a query, the one with the lowest index wins. Explain how much memory your intermediate arrays use at the largest sizes.
Part 2: Manhattan follow-up. Support metric = 'manhattan' (sum of absolute coordinate differences) through the same function. Which of your Part 1 speed-ups still apply, and can the switch change a prediction?
Part 3: Discussion (not graded by the tests). Show that Euclidean 1-NN is the same as taking the argmax of a single linear layer $Wx + b$ over the training points: give $W$ and $b$ in terms of the training data and say what that view is useful for.
Constraints
- $1 \le n, m \le 2000$, $1 \le d \le 64$; labels are ints.
- Coordinates are integers with absolute value up to $2 \cdot 10^9$ (think raw timestamps or ids), but within one call every feature spans at most 10,000 (largest minus smallest value over all training and query points).
- The answer must be exact, ties included.
Example 1
X_train = [[0, 0], [4, 0], [0, 3]], y_train = [7, 8, 9]
X_query = [[3, 1], [0, 1], [2, 0]]
euclidean -> [8, 7, 7]
manhattan -> [8, 7, 7]
The query (2, 0) is at squared distance 4 from both (0, 0) and (4, 0), so the lower index (label 7) wins.
Example 2
X_train = [[4, 4], [6, 0]], y_train = [1, 2], X_query = [[0, 0]]
euclidean -> [1] (squared distances 32 vs 36)
manhattan -> [2] (distances 8 vs 6)Show hint
Can you write the squared Euclidean distance as a sum of three terms, one of which covers every query-training pair at once?
Relevant roles: ML Engineer, Applied Scientist and Research Scientist.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium