Coding - Vectorized 1-NN and Neural Network Forward Pass

Problem Overview

This Machine Learning coding interview has been reported as a two-part question:

1. Implement 1-nearest-neighbor (1-NN) using only NumPy vectorized operations
2. Re-express the same 1-NN algorithm in terms of a neural network forward pass

Problem Statement

Part 1: Vectorized 1-NN

Given a dataset of points X and a query point x, implement the 1-nearest-neighbor algorithm using only NumPy vectorized operations. The goal is to find the point in X that is closest to x.

Input:

• X: A 2D NumPy array of shape (n_samples, n_features) representing the dataset points.
• x: A 1D NumPy array of shape (n_features,) representing the query point.

Output:

• The index of the closest point in X to x.

Part 2: Neural Network Forward Pass

Re-express the 1-NN algorithm from Part 1 in terms of a neural network forward pass. This involves defining a neural network architecture that can be used to compute the 1-NN.

Input:

• X: A 2D NumPy array of shape (n_samples, n_features) representing the dataset points.
• x: A 1D NumPy array of shape (n_features,) representing the query point.

Output:

• The index of the closest point in X to x.

Examples

Part 1: Vectorized 1-NN

Input: python X = np.array([[1, 2], [3, 4], [5, 6]]) x = np.array([2, 3])

Output: python 1

Part 2: Neural Network Forward Pass

Input: python X = np.array([[1, 2], [3, 4], [5, 6]]) x = np.array([2, 3])

Output: python 1

Constraints

• n_samples and n_features can be any positive integer.
• The dataset points X and query point x are non-empty.

Hints

1. For Part 1, use NumPy's broadcasting and vectorized operations to compute the pairwise distances between x and each point in X.
2. For Part 2, consider using a neural network with a single hidden layer and a final output layer with a softmax activation function.

Solution

Part 1: Vectorized 1-NN

`python import numpy as np

def vectorized_1nn(X, x): # Compute pairwise distances distances = np.linalg.norm(X - x, axis=1)

# Find the index of the closest point
closest_index = np.argmin(distances)

return closest_index

`

Part 2: Neural Network Forward Pass

`python import numpy as np import torch import torch.nn as nn import torch.nn.functional as F

class OneNN(nn.Module): def init(self, X): super(OneNN, self).init() self.X = X

def forward(self, x):
    # Compute pairwise distances
    distances = torch.norm(self.X - x, dim=1)
    
    # Find the index of the closest point
    closest_index = torch.argmin(distances)
    
    return closest_index

Example usage

X = np.array([[1, 2], [3, 4], [5, 6]]) x = np.array([2, 3])

Convert to PyTorch tensors

X_tensor = torch.tensor(X, dtype=torch.float32) x_tensor = torch.tensor(x, dtype=torch.float32)

Create the OneNN model

model = OneNN(X_tensor)

Forward pass

closest_index = model(x_tensor) `

Note: The above solution for Part 2 is a simple example and may require additional modifications to work with specific deep learning frameworks or use cases.