Bird
Raised Fist0

Implement ROC Curve and AUC from Predictions

CODINGintermediateInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
šŸ¤–
Implement ROC Curve and AUC from Predictions
Compute ROC and AUC from scratch using NumPy
codingintermediateFreq: very_highEvaluation Coding
Prerequisites:ROC-AUC vs PR-AUC
šŸ“
Problem Statement

Implement a function to compute the ROC curve and AUC from given true labels and predicted scores.

I/O Specification
Input:  true_labels: List[int], predicted_scores: List[float]
Output: roc_curve: Tuple[List[float], List[float]], auc: float
Example
{
  "input": "true_labels = [0, 0, 1, 1], predicted_scores = [0.1, 0.4, 0.35, 0.8]",
  "expected_output": "roc_curve = ([0.0, 0.5, 0.5, 1.0], [0.0, 0.0, 1.0, 1.0]), auc = 0.75"
}
šŸŽÆ
Interview Angles
  • Understanding of ROC and AUC concepts and their computation.
  • Ability to optimize naive implementations using sorting and cumulative sums.
  • Handling edge cases like all positive or all negative labels.
  • Implementing numerical integration techniques like the trapezoidal rule.
šŸ”µ
Naive Approach

Sort the predicted scores and iterate over each threshold to compute TPR and FPR manually.

Time: O(nĀ²) - Sorting is O(n log n), but computing TPR/FPR for each threshold is O(n) per threshold, leading to O(nĀ²) overall. Space: O(n) for storing TPR and FPR lists.
Why Insufficient
O(nĀ²) because it recomputes TPR/FPR for each threshold - fails for n > 10K
šŸ
Naive Code
Python
import numpy as np

def compute_roc_auc_naive(true_labels, predicted_scores):
    thresholds = np.sort(predicted_scores)[::-1]
    tpr_list = []
    fpr_list = []
    for threshold in thresholds:
        tp = fp = tn = fn = 0
        for i in range(len(true_labels)):
            if predicted_scores[i] >= threshold:
                if true_labels[i] == 1:
                    tp += 1
                else:
                    fp += 1
            else:
                if true_labels[i] == 1:
                    fn += 1
                else:
                    tn += 1
        tpr = tp / (tp + fn) if (tp + fn) > 0 else 0
        fpr = fp / (fp + tn) if (fp + tn) > 0 else 0
        tpr_list.append(tpr)
        fpr_list.append(fpr)
    auc = 0.0
    for i in range(1, len(fpr_list)):
        auc += (fpr_list[i] - fpr_list[i-1]) * (tpr_list[i] + tpr_list[i-1]) / 2
    return (fpr_list, tpr_list), auc

# Driver example
true_labels = [0, 0, 1, 1]
predicted_scores = [0.1, 0.4, 0.35, 0.8]
roc_curve, auc = compute_roc_auc_naive(true_labels, predicted_scores)
print(roc_curve, auc)
šŸ’”
Key Insight
Sort by predicted scores once, then compute TPR and FPR in a single pass using cumulative sums.
šŸ
Optimized Code
Python
import numpy as np

def compute_roc_auc_optimized(true_labels, predicted_scores):
    if len(true_labels) == 0:
        return ([], []), 0.0
    # Sort by predicted scores
    sorted_indices = np.argsort(predicted_scores)[::-1]
    sorted_labels = np.array(true_labels)[sorted_indices]
    sorted_scores = np.array(predicted_scores)[sorted_indices]
    # Calculate cumulative sums of positives and negatives
    cum_positives = np.cumsum(sorted_labels)
    total_positives = cum_positives[-1]
    total_negatives = len(true_labels) - total_positives
    # Initialize TPR and FPR lists
    tpr_list = [0.0]
    fpr_list = [0.0]
    # Iterate over sorted labels to compute TPR and FPR
    for i in range(len(sorted_labels)):
        if sorted_labels[i] == 1:
            tpr_list.append(cum_positives[i] / total_positives)
            fpr_list.append(fpr_list[-1])
        else:
            tpr_list.append(tpr_list[-1])
            fpr_list.append((i + 1 - cum_positives[i]) / total_negatives)
    # Calculate AUC using the trapezoidal rule
    auc = np.trapz(tpr_list, fpr_list)
    return (fpr_list, tpr_list), auc

# Driver example
true_labels = [0, 0, 1, 1]
predicted_scores = [0.1, 0.4, 0.35, 0.8]
roc_curve, auc = compute_roc_auc_optimized(true_labels, predicted_scores)
print(roc_curve, auc)
šŸ”
Line-by-Line
sorted_indices = np.argsort(predicted_scores)[::-1]
Sort indices of predicted scores in descending order to process highest scores first.
sorted_labels = np.array(true_labels)[sorted_indices]
Reorder true labels according to sorted predicted scores to align them.
cum_positives = np.cumsum(sorted_labels)
Compute cumulative sum of positives to track true positive count at each threshold.
total_positives = cum_positives[-1]
Total number of positive samples, used to normalize TPR.
total_negatives = len(true_labels) - total_positives
Total number of negative samples, used to normalize FPR.
tpr_list.append(cum_positives[i] / total_positives)
Append TPR for current threshold, calculated as cumulative positives over total positives.
fpr_list.append((i + 1 - cum_positives[i]) / total_negatives)
Append FPR for current threshold, calculated as cumulative negatives over total negatives.
auc = np.trapz(tpr_list, fpr_list)
Calculate AUC using the trapezoidal rule on the TPR and FPR lists.
āš”
Complexity
Time: O(n log n) - Sorting is O(n log n), and computing TPR/FPR is O(n) in a single pass. Space: O(n) for storing sorted indices and cumulative sums.
Output
([0.0, 0.0, 0.5, 1.0], [0.0, 0.5, 1.0, 1.0]), 0.75
šŸ”²
Edge Cases
All same class
If all true labels are the same, TPR or FPR will be undefined.
total_positives = cum_positives[-1]
Empty input
If inputs are empty, the function should return empty lists and AUC as 0.
if len(true_labels) == 0: return ([], []), 0.0
āš ļø
Common Mistakes
Not sorting predicted scores correctly.
Symptom: Incorrect ROC curve and AUC values.
Incorrect cumulative sum calculations.
Symptom: TPR and FPR values do not match expected results.
Not handling division by zero when computing TPR/FPR.
Symptom: Runtime errors or NaN values in output.
Misusing the trapezoidal rule for AUC calculation.
Symptom: AUC value significantly off from expected.

Practice

(1/5)
1. What does the following Python code output when implementing logistic regression with a sigmoid activation function?
import numpy as np

def sigmoid(z):
    return 1 / (1 + np.exp(-z))

z = np.array([0, 2, -2])
output = sigmoid(z)
print(output)
easy
A. [0.5, 0.88, 0.12]
B. [0.5, 0.88, 0.11]
C. [0.5, 0.87, 0.12]
D. [0.5, 0.86, 0.12]

Solution

  1. Step 1: Calculate sigmoid for each element

    Sigmoid function is applied element-wise: sigmoid(0) = 0.5, sigmoid(2) ā‰ˆ 0.88, sigmoid(-2) ā‰ˆ 0.12.

  2. Step 2: Check precision of calculations

    Common mistake is rounding errors. Correct values are [0.5, 0.880797, 0.119203], rounded to [0.5, 0.88, 0.12].

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Sigmoid(0)=0.5, Sigmoid(2)ā‰ˆ0.88, Sigmoid(-2)ā‰ˆ0.12 [OK]
Hint: Sigmoid(0)=0.5, Sigmoid(2)ā‰ˆ0.88, Sigmoid(-2)ā‰ˆ0.12 [OK]
Common Mistakes:
2. What is the time complexity of calculating the mean Average Precision (mAP) for a single image with N predicted bounding boxes and M ground truth boxes?
easy
A. O(N + M)
B. O(N^2)
C. O(N * M)
D. O(M^2)

Solution

  1. Step 1: Understand the Process

    For each predicted box, IoU is calculated with each ground truth box, leading to N * M comparisons.

  2. Step 2: Determine Complexity

    Each comparison is constant time, so the overall complexity is O(N * M).

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    IoU comparisons drive complexity [OK]
Hint: IoU comparisons drive complexity [OK]
Common Mistakes:
3. You implemented stratified K-Fold cross-validation but notice class imbalance in some folds. What is the most likely cause?
medium
A. Incorrect stratification parameter
B. Data shuffling before splitting
C. Incorrect number of splits
D. Too many folds for the dataset size

Solution

  1. Step 1: Identify stratification issue

    Stratification ensures class distribution is preserved in each fold.

  2. Step 2: Eliminate wrong options

    Incorrect number of splits and D relate to fold count, not class distribution. Data shuffling before splitting affects randomness, not stratification.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Check stratification parameter for class balance. [OK]
Hint: Check stratification parameter for class balance. [OK]
Common Mistakes:
4. A logistic regression model is not converging during training. Which line in the code is most likely causing the issue?
import numpy as np

# Initialize weights
weights = np.zeros((m, 1))

# Training loop
for epoch in range(epochs):
    # Compute predictions
    predictions = 1 / (1 + np.exp(-np.dot(X, weights)))
    
    # Compute gradient
    gradient = np.dot(X.T, (predictions - y)) / n
    
    # Update weights
    weights -= learning_rate * gradient
medium
A. weights -= learning_rate * gradient
B. predictions = 1 / (1 + np.exp(-np.dot(X, weights)))
C. weights = np.zeros((m, 1))
D. gradient = np.dot(X.T, (predictions - y)) / n

Solution

  1. Step 1: Identify potential issues

    Convergence issues often arise from incorrect weight updates or learning rate problems.

  2. Step 2: Analyze weight update line

    If learning_rate is too high, weights update too aggressively, causing divergence.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Check learning rate in weight updates [OK]
Hint: Check learning rate in weight updates [OK]
Common Mistakes:
5. How can you optimize the NDCG calculation for large datasets?
hard
A. Use a parallel processing library to compute DCG.
B. Use a more efficient sorting algorithm.
C. Precompute log values for positions.
D. Reduce the number of relevance scores considered.

Solution

  1. Step 1: Identify Bottlenecks

    Calculating log values repeatedly can be computationally expensive.

  2. Step 2: Optimize Calculation

    Precomputing log values for positions reduces redundant calculations.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Precompute logs for efficiency. [OK]
Hint: Precompute logs for efficiency. [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