Bird
Raised Fist0

NDCG vs DCG for Ranking Evaluation

CODINGintermediateInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
⚖️
NDCG vs DCG

When evaluating a search engine's ranking performance, would you use NDCG or DCG? Justify your choice.

📊
Comparison
DimensionNDCGDCG
NormalizationYesNo
InterpretabilityModerateLow
Computational ComplexityHigherLower
Cross-query ComparisonYesNo
Bounded MetricYesNo
✅
Verdict
Default to NDCG when evaluating multiple queries with consistent relevance scales and when normalized scores are needed. Use DCG for simpler, single-query evaluations where computational efficiency is a priority.
💡
Key Insight
NDCG's normalization allows for cross-query comparison, making it ideal for evaluating search engines across diverse queries.
⚠️
Interview Trap
❌ Wrong: Always use NDCG because it's normalized.
Ignoring the computational overhead and the need for a perfect ranking for normalization.
✅ Consider the number of queries and the consistency of the relevance scale before choosing NDCG over DCG.
NDCG
"Normalizes the ranking score to allow comparison across different queries."
Weaknesses
  • Requires a perfect ranking for normalization, which may not always be available.
  • More computationally intensive due to normalization step.
  • Less intuitive interpretation compared to raw DCG scores.
Ideal When
  • When comparing rankings across multiple queries (n > 100).
  • When the relevance scale is consistent across queries.
  • When you need a bounded metric (0 to 1) for easier interpretation.
Google uses NDCG to evaluate search result rankings across different queries to ensure consistent performance.
DCG
"Provides a straightforward measure of ranking quality without needing a perfect ranking."
Weaknesses
  • Scores are not normalized, making it hard to compare across queries.
  • Can be misleading if the relevance scale varies between queries.
  • Does not provide a bounded metric, making interpretation less intuitive.
Ideal When
  • When evaluating a single query or a small number of queries (n < 100).
  • When the relevance scale is not consistent across queries.
  • When computational simplicity is a priority.
Amazon uses DCG to evaluate product recommendation rankings for individual user queries where normalization is not required.
🐍
NDCG - Example
▼ Show
Python
import numpy as np

def ndcg(relevance_scores):
    dcg = np.sum((2**relevance_scores - 1) / np.log2(np.arange(2, len(relevance_scores) + 2)))
    ideal_dcg = np.sum((2**np.sort(relevance_scores)[::-1] - 1) / np.log2(np.arange(2, len(relevance_scores) + 2)))
    return dcg / ideal_dcg if ideal_dcg > 0 else 0

relevance_scores = [3, 2, 3, 0, 1, 2]
print(ndcg(relevance_scores))
🐍
DCG - Example
▼ Show
Python
import numpy as np

def dcg(relevance_scores):
    return np.sum((2**relevance_scores - 1) / np.log2(np.arange(2, len(relevance_scores) + 2)))

relevance_scores = [3, 2, 3, 0, 1, 2]
print(dcg(relevance_scores))
✅
Use NDCG When
  • •When n > 100 and you need to compare across multiple queries.
  • •When the relevance scale is consistent across queries.
  • •When you need a bounded metric for easier interpretation.
✅
Use DCG When
  • •When n < 100 and evaluating individual queries.
  • •When the relevance scale varies between queries.
  • •When computational simplicity is a priority.
↳
Nuances
  • NDCG is preferred when you need to compare performance across different queries, even if they have different lengths.
  • DCG can be misleading if used to compare queries with different relevance scales, as it does not normalize scores.
  • In cases where computational resources are limited, DCG might be preferred due to its simplicity.

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. What does the following Python code snippet output when implementing the Skip-Gram model with negative sampling? 
import numpy as np

vocab_size = 5
embedding_dim = 3

# Initialize random embeddings
embeddings = np.random.rand(vocab_size, embedding_dim)

# Select a word index
word_index = 2

# Get the embedding for the word
word_embedding = embeddings[word_index]

print(word_embedding.shape)
easy
A. (3, 5)
B. (5, 3)
C. (3,)
D. (1, 3)

Solution

  1. Step 1: Understand the code

    The code initializes a random embedding matrix of shape (vocab_size, embedding_dim) and retrieves the embedding for a specific word index.

  2. Step 2: Determine the shape of the retrieved embedding

    The embedding for a single word is a 1D array with length equal to embedding_dim, hence the shape is (3,).

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Single word embedding shape is (embedding_dim,) [OK]
Hint: Single word embedding shape is (embedding_dim,) [OK]
Common Mistakes:
3. You implemented linear regression using gradient descent, but the model is not converging. What is the most likely cause?
medium
A. The learning rate is too low.
B. The learning rate is too high.
C. The dataset is too small.
D. The model has too many features.

Solution

  1. Step 1: Identify symptoms of non-convergence

    Non-convergence often results from oscillations due to a high learning rate.

  2. Step 2: Eliminate other options

    Low learning rate causes slow convergence, not non-convergence. Dataset size and feature count affect overfitting, not convergence.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    High learning rate causes oscillations. [OK]
Hint: High learning rate causes oscillations. [OK]
Common Mistakes:
4. A candidate implemented the cross-entropy loss function but it returns negative values. What is the most likely cause?
medium
A. The input probabilities are not normalized.
B. The log function is applied incorrectly.
C. The softmax function is not applied before the loss calculation.
D. The loss function is missing a regularization term.

Solution

  1. Step 1: Identify negative values cause

    Cross-entropy loss should be non-negative; negative values suggest log issues.

  2. Step 2: Check log application

    Log applied to values outside (0,1) can cause negatives.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Log of non-probabilities causes negatives [OK]
Hint: Log of non-probabilities causes negatives [OK]
Common Mistakes:
5. How can you optimize the implementation of K-Fold cross-validation to reduce computational overhead?
hard
A. Use fewer folds
B. Increase the number of epochs
C. Use a smaller dataset
D. Parallelize the training process

Solution

  1. Step 1: Identify optimization strategies

    Parallelizing the training process can significantly reduce computation time.

  2. Step 2: Eliminate wrong options

    Use fewer folds reduces validation quality. Use a smaller dataset affects model performance. Increase the number of epochs increases computation.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Parallelize to optimize K-Fold. [OK]
Hint: Parallelize to optimize K-Fold. [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