Bird
Raised Fist0

Implement Softmax and Cross-Entropy Loss

CODINGbeginnerInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Implement Softmax and Cross-Entropy Loss
Master the implementation of softmax and cross-entropy loss from scratch using NumPy.
codingbeginnerFreq: very_highEvaluation Coding
Prerequisites:Logistic RegressionActivation Functions
📝
Problem Statement

Implement the softmax function and cross-entropy loss from scratch. The softmax function should take a 2D NumPy array of logits and return a 2D array of probabilities. The cross-entropy loss should take the predicted probabilities and the true labels and return the average loss.

I/O Specification
Input:  logits: np.ndarray of shape (n_samples, n_classes), labels: np.ndarray of shape (n_samples,)
Output: loss: float
Example
logits = np.array([[2.0, 1.0, 0.1]]), labels = np.array([0]) → expected output: 0.5514447139320511
🎯
Interview Angles
  • Testing understanding of softmax and its numerical stability issues.
  • Evaluating ability to implement vectorized operations using NumPy.
  • Assessing knowledge of cross-entropy loss and its application in classification tasks.
  • Checking for understanding of broadcasting and indexing in NumPy.
🔵
Naive Approach

Compute the softmax probabilities by iterating over each sample and class, applying the softmax formula. Then, compute the cross-entropy loss by iterating over each sample, calculating the negative log likelihood for the true class.

Time: O(n_samples * n_classes) - iterating over each sample and class. Space: O(n_samples * n_classes) - storing probabilities.
Why Insufficient
O(n_samples * n_classes) because it uses explicit loops over samples and classes, which is inefficient for large datasets.
🐍
Naive Code
Python
import numpy as np

def softmax_naive(logits):
    n_samples, n_classes = logits.shape
    probabilities = np.zeros_like(logits)
    for i in range(n_samples):
        exp_logits = np.exp(logits[i] - np.max(logits[i]))
        probabilities[i] = exp_logits / np.sum(exp_logits)
    return probabilities


def cross_entropy_loss_naive(probabilities, labels):
    n_samples = probabilities.shape[0]
    loss = 0.0
    for i in range(n_samples):
        loss -= np.log(probabilities[i, labels[i]])
    return loss / n_samples

# Driver example
logits = np.array([[2.0, 1.0, 0.1]])
labels = np.array([0])
probs = softmax_naive(logits)
loss = cross_entropy_loss_naive(probs, labels)
print(loss)  # Output: 0.5514447139320511
💡
Key Insight
Use NumPy's vectorized operations to compute the softmax probabilities and cross-entropy loss in a single pass without explicit loops.
🐍
Optimized Code
Python
import numpy as np

def softmax(logits):
    exp_logits = np.exp(logits - np.max(logits, axis=1, keepdims=True))
    return exp_logits / np.sum(exp_logits, axis=1, keepdims=True)


def cross_entropy_loss(probabilities, labels):
    n_samples = probabilities.shape[0]
    log_likelihood = -np.log(probabilities[np.arange(n_samples), labels])
    return np.mean(log_likelihood)

# Driver example
logits = np.array([[2.0, 1.0, 0.1]])
labels = np.array([0])
probs = softmax(logits)
loss = cross_entropy_loss(probs, labels)
print(loss)  # Output: 0.5514447139320511
🔍
Line-by-Line
exp_logits = np.exp(logits - np.max(logits, axis=1, keepdims=True))
Subtracting max for numerical stability - prevents overflow in exp.
return exp_logits / np.sum(exp_logits, axis=1, keepdims=True)
Normalizes the exponentials to sum to 1 - computes softmax probabilities.
log_likelihood = -np.log(probabilities[np.arange(n_samples), labels])
Selects the log probability of the true class for each sample.
return np.mean(log_likelihood)
Averages the negative log likelihoods - computes the mean cross-entropy loss.
np.arange(n_samples)
Generates indices for each sample - used to index the correct class probability.
⚡
Complexity
Time: O(n_samples * n_classes) - vectorized operations over the entire matrix. Space: O(n_samples * n_classes) - storing intermediate results.
Output
0.5514447139320511
🔲
Edge Cases
Single class
Softmax should return 1 for the single class, and cross-entropy should be 0 if predicted correctly.
exp_logits = np.exp(logits - np.max(logits, axis=1, keepdims=True))
Numerical stability
Subtracting the max value prevents overflow in the exponential calculation.
logits - np.max(logits, axis=1, keepdims=True)
⚠️
Common Mistakes
Forgetting to subtract the max value for numerical stability.
Symptom: Results in NaN or Inf values due to overflow in exp.
Incorrect indexing when calculating log likelihood.
Symptom: Results in incorrect loss values.
Not using keepdims=True when summing for softmax normalization.
Symptom: Shape mismatch errors during division.
Using loops instead of vectorized operations.
Symptom: Inefficient code that is slow on large datasets.

Practice

(1/5)
1. What is the time complexity of the forward pass of batch normalization for a dataset with n samples and d features?
easy
A. O(n + d)
B. O(n^2)
C. O(d^2)
D. O(n * d)

Solution

  1. Step 1: Analyze the operations

    Batch normalization involves computing mean and variance, both O(n * d) operations.

  2. Step 2: Consider the normalization step

    Normalizing each feature is also O(n * d).

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Batch norm: O(n * d) for mean/variance [OK]
Hint: Batch norm: O(n * d) for mean/variance [OK]
Common Mistakes:
2. 
import numpy as np

data = np.array([1, 2, 3, 4, 5])
mean = np.mean(data)
std = np.std(data)

standardized_data = (data - mean) / std
print(standardized_data)
What does the code output?
easy
A. An array with values [0, 1, 2, 3, 4]
B. An array with values [0, 0.5, 1, 1.5, 2]
C. An array with values [-1.41, -0.71, 0, 0.71, 1.41]
D. An array with values [-2, -1, 0, 1, 2]

Solution

  1. Step 1: Understand Standardization

    Standardization transforms data to have a mean of 0 and a standard deviation of 1.

  2. Step 2: Calculate the Output

    The standardized values are calculated as (data - mean) / std, resulting in [-1.41, -0.71, 0, 0.71, 1.41].

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Standardization centers data around 0. [OK]
Hint: Standardization centers data around 0. [OK]
Common Mistakes:
3. What does the following Python code snippet output when calculating the Intersection over Union (IoU) for two bounding boxes? 
import numpy as np

def iou(box1, box2):
    x1 = max(box1[0], box2[0])
    y1 = max(box1[1], box2[1])
    x2 = min(box1[2], box2[2])
    y2 = min(box1[3], box2[3])
    intersection = max(0, x2 - x1) * max(0, y2 - y1)
    area1 = (box1[2] - box1[0]) * (box1[3] - box1[1])
    area2 = (box2[2] - box2[0]) * (box2[3] - box2[1])
    union = area1 + area2 - intersection
    return intersection / union

box1 = [0, 0, 2, 2]
box2 = [1, 1, 3, 3]
print(iou(box1, box2))
easy
A. 0.14285714285714285
B. 0.3333333333333333
C. 0.5
D. 0.25

Solution

  1. Step 1: Calculate Intersection and Union

    The intersection area is 1 (from (1,1) to (2,2)). The union area is 7 (4 from box1 + 4 from box2 - 1 intersection).

  2. Step 2: Calculate IoU

    IoU = 1/7 = 0.14285714285714285.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Intersection over Union formula [OK]
Hint: Intersection over Union formula [OK]
Common Mistakes:
4. In a multi-class classification problem, how should you modify the confusion matrix implementation to handle more than two classes?
medium
A. Use a 2x2 matrix and sum over classes.
B. Use a 3D matrix to capture all interactions.
C. Use separate matrices for each class.
D. Use a matrix of size (n_classes, n_classes).

Solution

  1. Step 1: Understand multi-class needs

    Each class needs its own row and column in the matrix.

  2. Step 2: Choose correct matrix size

    A (n_classes, n_classes) matrix captures all class interactions.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Multi-class needs (n_classes, n_classes) matrix. [OK]
Hint: Multi-class needs (n_classes, n_classes) matrix. [OK]
Common Mistakes:
5. You need to apply non-max suppression on a batch of images. Which approach is most efficient?
medium
A. Apply non-max suppression independently on each image.
B. Concatenate all boxes from all images and apply non-max suppression once.
C. Apply non-max suppression on the image with the highest number of boxes only.
D. Apply non-max suppression on images with scores above a certain threshold.

Solution

  1. Step 1: Consider independence of images

    Each image's boxes are independent, so process them separately.

  2. Step 2: Evaluate efficiency

    Concatenating boxes would mix unrelated data, and focusing on one image or thresholding scores misses other valid boxes.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Process each image independently [OK]
Hint: Process each image independently [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard