Top-K Accuracy Check

You want to check whether the true class index is within the top-k highest scores in a prediction vector.

---

1. Background Knowledge

In a multi-class image classification task, a model outputs a score (often a logit or probability) for each possible class. For an input image, you might get a vector like:

$$\text{scores} = [s_0, s_1, \dots, s_{C-1}]$$

where $C$ is the number of classes, and $s_i$ is how confident the model is that the image belongs to class $i$.

Top-1 accuracy checks whether the single highest-scoring class matches the true class label. This can be strict: if the correct class is the second highest score, it’s counted as wrong. Top-k accuracy relaxes this: it is counted as correct if the true class is among the k highest-scoring classes. This is especially useful in fine-grained or large-label-space tasks (like ImageNet) where several classes are visually similar, so “the right answer is in the top few guesses” is still informative.

---

2. Algorithm / General Approach

The pattern for a single example:

1. Rank classes by their prediction scores in descending order.
2. Select the top k class indices.
3. Check membership: return true/1 if the true class index is in this set; otherwise false/0.

For a batch, you repeat this per example and average the results to get top-k accuracy.

---

3. Step-by-Step Strategy

Assume:

• scores is a list/array of length n_classes.
• true_idx is the integer index of the true class.
• k is the integer for “top-k”.

Step-by-step:

1. Pair scores with indices Create pairs (score, index) so you remember which class each score belongs to.

2. Sort by score descending Sort the pairs by score from largest to smallest.

3. Take top-k indices

• Slice the first k elements after sorting.
• Extract their class indices into something like top_indices.

4. Check if true class is included

• Check true_idx in top_indices.
• If yes, the prediction is top-k correct; otherwise it’s incorrect.

In code form (Python-like, conceptual):

def is_top_k_correct(scores, true_idx, k):
 # 1. pair scores with indices
 indexed = list(enumerate(scores)) # [(0, s0), (1, s1),...]

 # 2. sort by score descending
 indexed.sort(key=lambda x: x, reverse=True)

 # 3. take top-k indices
 top_k_indices = [idx for idx, _ in indexed[:k]]

 # 4. membership check
 return true_idx in top_k_indices

---

4. Common Pitfalls

• Using ascending sort by mistake: always sort descending so highest scores come first.
• Off-by-one with k:
• Ensure k >= 1 and typically k <= number_of_classes.
• If k is larger than the number of classes, you should handle or clamp it.
• Confusing class labels vs indices:
• Make sure true_idx corresponds to the position of the class in the scores array, not some arbitrary label id unless you have mapped it.
• Floating-point ties:
• Rarely critical for simple problems; just rely on the sort’s tie-breaking.
• Inefficient full sort for large n:
• For very large numbers of classes, you can use a partial selection (like a max-heap or nth_element / nlargest) to get top-k without fully sorting. For an “Easy” problem, a full sort is fine.

---

5. Time & Space Complexity

Let $C$ be the number of classes.

• Full sort approach:

• Time: $O(C \log C)$ (sorting all class scores).

• Space: $O(C)$ for storing the paired (index, score) or a copy.

• Using selection/top-k algorithms (optional optimization):

• Time: $O(C \log k)$ using a size-$k$ heap, or average $O(C)$ with specialized selection.

• Space: $O(C)$ or $O(k)$, depending on implementation.

For typical small/medium C in an Easy-level problem, $O(C \log C)$ with a simple sort is completely acceptable and easiest to implement.