Bird
Raised Fist0

Implement NDCG for Ranking Evaluation

CODINGintermediateInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
▶
Execution Trace
Step 1/4
Relevance Scores

Initial relevance scores are [3, 2, 3, 0, 1, 2]

🎯 Understanding the input relevance scores is crucial for calculating DCG.
relevance_scores = [3, 2, 3, 0, 1, 2]
DCG Calculation

DCG is calculated as 6.261 using logarithmic discounting.

🎯 DCG uses a logarithmic scale to discount lower-ranked items.
import math
dcg = relevance_scores[0]
for i in range(1, len(relevance_scores)):
    dcg += relevance_scores[i] / math.log2(i + 1)
Ideal DCG Calculation

Ideal DCG is calculated as 6.861 for perfect ranking.

🎯 IDCG represents the best possible DCG with perfect ranking.
ideal_relevance = sorted(relevance_scores, reverse=True)
idcg = ideal_relevance[0]
for i in range(1, len(ideal_relevance)):
    idcg += ideal_relevance[i] / math.log2(i + 1)
NDCG Calculation

NDCG is calculated as 0.912 by dividing DCG by IDCG.

🎯 NDCG normalizes DCG to a scale of 0 to 1.
ndcg = dcg / idcg
📊
Diagram
Diagram
┌──────────────────────────────────────────────────────────────┐
│                        NDCG Calculation                      │
├──────────────────────────────────────────────────────────────┤
│  Relevance Scores: [3, 2, 3, 0, 1, 2]                        │
│  Ideal DCG: 6.861                                            │
│                                                              │
│  Step 1: DCG Calculation                                     │
│  DCG = 3 + 2/log2(3) + 3/log2(4) + 0/log2(5) + 1/log2(6) +   │
│        2/log2(7) = 6.261                                     │
│                                                              │
│  Step 2: NDCG Calculation                                    │
│  NDCG = DCG / IDCG = 6.261 / 6.861 = 0.912                   │
└──────────────────────────────────────────────────────────────┘
Labels
  • Relevance Scores: The input scores indicating relevance
  • DCG Calculation: The process of computing discounted cumulative gain
  • NDCG Calculation: Normalizing DCG by the ideal DCG
🔑
Key Moments
▲
Q: Why is logarithmic discounting used in DCG calculation?
A: Logarithmic discounting reduces the impact of lower-ranked items, reflecting their lesser importance.
Q: How does the ideal DCG (IDCG) influence the NDCG score?
A: IDCG provides a benchmark for the best possible DCG, allowing NDCG to measure the quality of the ranking.
Q: What does an NDCG score of 1 indicate?
A: An NDCG score of 1 indicates a perfect ranking where the order of items matches the ideal ranking.
Trace Summary

The diagram and trace illustrate the process of calculating the Normalized Discounted Cumulative Gain (NDCG) for ranking evaluation. Starting with a set of relevance scores, the Discounted Cumulative Gain (DCG) is computed using logarithmic discounting to account for the position of each item. The Ideal DCG (IDCG) is then calculated for a perfectly ranked list. Finally, the NDCG is obtained by dividing the DCG by the IDCG, providing a normalized score between 0 and 1 that reflects the quality of the ranking. This process is crucial for evaluating the effectiveness of ranking algorithms.

Primary Focus

✓ Implementing NDCG for ranking evaluation

Practice

(1/5)
1. What is the time complexity of computing the forward pass for a single layer in a neural network using NumPy?
easy
A. O(n^2)
B. O(n)
C. O(n log n)
D. O(1)

Solution

  1. Step 1: Identify operations

    Forward pass involves matrix-vector multiplication.

  2. Step 2: Determine complexity

    Matrix-vector multiplication is O(n) where n is the number of neurons.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Matrix-vector multiplication is O(n) [OK]
Hint: Matrix-vector multiplication is O(n) [OK]
Common Mistakes:
2. You implemented early stopping in your training loop, but the model still overfits. What is the most likely reason?
medium
A. The validation set is too small.
B. The learning rate is too high.
C. The patience parameter is too low.
D. The model architecture is too simple.

Solution

  1. Step 1: Analyze early stopping behavior

    Early stopping relies on validation performance to halt training.

  2. Step 2: Identify the root cause of overfitting

    If the validation set is too small, it may not accurately reflect generalization, leading to overfitting despite early stopping.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Small validation set can mislead early stopping. [OK]
Hint: Small validation set can mislead early stopping. [OK]
Common Mistakes:
3. 
def calculate_f1(confusion_matrix):
    tp = confusion_matrix[0, 0]
    fp = confusion_matrix[1, 0]
    fn = confusion_matrix[0, 1]
    precision = tp / (tp + fp)
    recall = tp / (tp + fn)
    f1_score = 2 * (precision * recall) / (precision + recall)
    return f1_score

confusion_matrix = np.array([[50, 10], [5, 35]])
print(calculate_f1(confusion_matrix))
medium
A. 0.9091
B. 0.8696
C. 0.8333
D. Throws a division by zero error

Solution

  1. Step 1: Calculate precision and recall

    Precision = 0.9091, Recall = 0.8333.

  2. Step 2: Calculate F1-score

    F1 = 2 * (0.9091 * 0.8333) / (0.9091 + 0.8333) = 0.8696.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    F1 combines precision and recall. [OK]
Hint: F1 combines precision and recall. [OK]
Common Mistakes:
4. How can you optimize the backward pass of batch normalization to improve computational efficiency?
hard
A. Fuse batch normalization with preceding linear layers.
B. Pre-compute gradients for all layers.
C. Use a smaller batch size to reduce computation.
D. Use a higher learning rate to speed up convergence.

Solution

  1. Step 1: Identify optimization techniques

    Fusing operations can reduce computational overhead.

  2. Step 2: Evaluate each option

    Fusing batch normalization with linear layers reduces redundant computations.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Fuse layers to optimize batch norm [OK]
Hint: Fuse layers to optimize batch norm [OK]
Common Mistakes:
5. How can you optimize the computation of eigenvectors for a large covariance matrix in PCA?
hard
A. Use the full SVD decomposition.
B. Use the power iteration method.
C. Use the Gram-Schmidt process.
D. Use incremental PCA.

Solution

  1. Step 1: Identify efficient eigenvector computation methods

    The power iteration method is efficient for finding the largest eigenvectors of large matrices.

  2. Step 2: Eliminate wrong options

    Use the full SVD decomposition. is computationally expensive. Use incremental PCA. is for streaming data, not large matrices. Use the Gram-Schmidt process. is for orthogonalization, not eigenvector computation.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Power iteration for large matrix eigenvectors. [OK]
Hint: Power iteration for large matrix eigenvectors. [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