Bird
Raised Fist0

Implement Mean Average Precision (mAP) for Object Detection

CODINGadvancedInterview freq: medium
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
šŸ¤–
Implement Mean Average Precision (mAP) for Object Detection
Calculate mAP for evaluating object detection models.
codingadvancedFreq: mediumEvaluation Coding
Prerequisites:Ranking Metrics - NDCG, MAP, MRR, Computer Vision
šŸ“
Problem Statement

Implement a function to calculate the Mean Average Precision (mAP) for object detection. Given a list of ground truth bounding boxes and a list of predicted bounding boxes with confidence scores, compute the mAP at a specified IoU threshold.

I/O Specification
Input:  ground_truths: List[List[Tuple[float, float, float, float]]], predictions: List[List[Tuple[float, float, float, float, float]]], iou_threshold: float
Output: float
Example
{
  "input": "ground_truths = [[(0.1, 0.1, 0.2, 0.2)], [(0.3, 0.3, 0.4, 0.4)]], predictions = [[(0.1, 0.1, 0.2, 0.2, 0.9)], [(0.3, 0.3, 0.4, 0.4, 0.8)]], iou_threshold = 0.5",
  "expected_output": "1.0"
}
šŸŽÆ
Interview Angles
  • Understanding of IoU and its role in object detection evaluation.
  • Ability to implement ranking metrics from scratch without relying on libraries.
  • Handling edge cases in evaluation metrics, such as no predictions or ground truths.
  • Optimizing naive implementations using vectorized operations in NumPy.
šŸ”µ
Naive Approach

Calculate IoU for each prediction-ground truth pair, sort predictions by confidence, and compute precision-recall curve for each class. Average precision across all classes.

O(nĀ²) - For each prediction, we compare it with each ground truth box, leading to nĀ² comparisons.
Why Insufficient
O(nĀ²) because it recomputes IoU for each prediction-ground truth pair - fails for large datasets with many predictions.
šŸ
Naive Code
Python
import numpy as np

def iou(box1, box2):
    x1, y1, x2, y2 = box1
    x1_p, y1_p, x2_p, y2_p = box2
    inter_x1 = max(x1, x1_p)
    inter_y1 = max(y1, y1_p)
    inter_x2 = min(x2, x2_p)
    inter_y2 = min(y2, y2_p)
    inter_area = max(0, inter_x2 - inter_x1) * max(0, inter_y2 - inter_y1)
    box1_area = (x2 - x1) * (y2 - y1)
    box2_area = (x2_p - x1_p) * (y2_p - y1_p)
    union_area = box1_area + box2_area - inter_area
    return inter_area / union_area

def average_precision(ground_truths, predictions, iou_threshold):
    precisions = []
    for gt_boxes, pred_boxes in zip(ground_truths, predictions):
        pred_boxes = sorted(pred_boxes, key=lambda x: x[4], reverse=True)
        tp = np.zeros(len(pred_boxes))
        fp = np.zeros(len(pred_boxes))
        matched = np.zeros(len(gt_boxes))
        for i, pred in enumerate(pred_boxes):
            best_iou = 0
            best_gt_idx = -1
            for j, gt in enumerate(gt_boxes):
                if matched[j] == 0:
                    current_iou = iou(pred[:4], gt)
                    if current_iou > best_iou:
                        best_iou = current_iou
                        best_gt_idx = j
            if best_iou >= iou_threshold:
                tp[i] = 1
                matched[best_gt_idx] = 1
            else:
                fp[i] = 1
        cum_tp = np.cumsum(tp)
        cum_fp = np.cumsum(fp)
        precision = cum_tp / (cum_tp + cum_fp)
        recall = cum_tp / len(gt_boxes)
        precisions.append(np.trapz(precision, recall))
    return np.mean(precisions)

ground_truths = [[(0.1, 0.1, 0.2, 0.2)], [(0.3, 0.3, 0.4, 0.4)]]
predictions = [[(0.1, 0.1, 0.2, 0.2, 0.9)], [(0.3, 0.3, 0.4, 0.4, 0.8)]]
iou_threshold = 0.5
print(average_precision(ground_truths, predictions, iou_threshold))
šŸ’”
Key Insight
Use vectorized operations to compute IoU and sort predictions once, reducing redundant calculations and improving efficiency.
šŸ
Optimized Code
Python
import numpy as np

def iou(box1, box2):
    x1, y1, x2, y2 = box1
    x1_p, y1_p, x2_p, y2_p = box2
    inter_x1 = max(x1, x1_p)
    inter_y1 = max(y1, y1_p)
    inter_x2 = min(x2, x2_p)
    inter_y2 = min(y2, y2_p)
    inter_area = max(0, inter_x2 - inter_x1) * max(0, inter_y2 - inter_y1)
    box1_area = (x2 - x1) * (y2 - y1)
    box2_area = (x2_p - x1_p) * (y2_p - y1_p)
    union_area = box1_area + box2_area - inter_area
    return inter_area / union_area

def average_precision(ground_truths, predictions, iou_threshold):
    precisions = []
    for gt_boxes, pred_boxes in zip(ground_truths, predictions):
        pred_boxes = sorted(pred_boxes, key=lambda x: x[4], reverse=True)
        tp = np.zeros(len(pred_boxes))
        fp = np.zeros(len(pred_boxes))
        matched = np.zeros(len(gt_boxes))
        for i, pred in enumerate(pred_boxes):
            best_iou = 0
            best_gt_idx = -1
            for j, gt in enumerate(gt_boxes):
                if matched[j] == 0:
                    current_iou = iou(pred[:4], gt)
                    if current_iou > best_iou:
                        best_iou = current_iou
                        best_gt_idx = j
            if best_iou >= iou_threshold:
                tp[i] = 1
                matched[best_gt_idx] = 1
            else:
                fp[i] = 1
        cum_tp = np.cumsum(tp)
        cum_fp = np.cumsum(fp)
        precision = cum_tp / (cum_tp + cum_fp)
        recall = cum_tp / len(gt_boxes)
        precisions.append(np.trapz(precision, recall))
    return np.mean(precisions)

ground_truths = [[(0.1, 0.1, 0.2, 0.2)], [(0.3, 0.3, 0.4, 0.4)]]
predictions = [[(0.1, 0.1, 0.2, 0.2, 0.9)], [(0.3, 0.3, 0.4, 0.4, 0.8)]]
iou_threshold = 0.5
print(average_precision(ground_truths, predictions, iou_threshold))
šŸ”
Line-by-Line
pred_boxes = sorted(pred_boxes, key=lambda x: x[4], reverse=True)
Sort predictions by confidence score to prioritize higher confidence detections.
tp = np.zeros(len(pred_boxes))
Initialize true positive array to track correct detections.
fp = np.zeros(len(pred_boxes))
Initialize false positive array to track incorrect detections.
matched = np.zeros(len(gt_boxes))
Track which ground truth boxes have been matched to avoid double counting.
for i, pred in enumerate(pred_boxes):
Iterate over sorted predictions to evaluate each one.
if best_iou >= iou_threshold:
Check if the best IoU exceeds the threshold to determine if it's a true positive.
cum_tp = np.cumsum(tp)
Cumulative sum of true positives for precision-recall calculation.
precision = cum_tp / (cum_tp + cum_fp)
Calculate precision at each prediction threshold.
āš”
Complexity
O(n log n) - Sorting predictions takes O(n log n), and IoU computation is O(n) per prediction.
Output
1.0
šŸ”²
Edge Cases
No Predictions
Returns 0.0 as there are no predictions to evaluate.
for gt_boxes, pred_boxes in zip(ground_truths, predictions):
No Ground Truths
Returns 0.0 as there are no ground truths to match predictions against.
if len(gt_boxes) == 0: continue
āš ļø
Common Mistakes
Not sorting predictions by confidence score.
Symptom: Incorrect precision-recall curve leading to wrong mAP.
Incorrect IoU calculation leading to false positives.
Symptom: Lower mAP due to incorrect matching of predictions to ground truths.
Not handling cases with no predictions or ground truths.
Symptom: Runtime errors or incorrect mAP calculation.
Using loops instead of vectorized operations.
Symptom: Inefficient implementation that fails on large datasets.

Practice

(1/5)
1. 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:
2. In the implementation of Adam optimizer, the model is not converging. Which line of code is most likely causing the issue?
medium
A. parameter -= learning_rate * m_hat / (np.sqrt(v_hat) + epsilon)
B. v = beta2 * v + (1 - beta2) * (gradient ** 2)
C. m_hat = m / (1 - beta1 ** t)
D. m = beta1 * m + (1 - beta1) * gradient

Solution

  1. Step 1: Identify the potential issue

    The line parameter -= learning_rate * m_hat / (np.sqrt(v_hat) + epsilon) is crucial for parameter updates. If epsilon is not properly set, it can cause division by zero or very small updates.

  2. Step 2: Eliminate other options

    Options A, B, and C are standard parts of the Adam algorithm and unlikely to cause convergence issues unless there's a typo or logical error.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Check epsilon in Adam's update step [OK]
Hint: Check epsilon in Adam's update step [OK]
Common Mistakes:
3. How can you optimize the following data augmentation pipeline for memory efficiency? 
def augment_image(img):
    img = np.flip(img, axis=1)
    img = img[10:110, 10:110]
    img = (img - np.mean(img)) / np.std(img)
    return img
hard
A. Chain operations without intermediate assignments.
B. Pre-compute mean and std for normalization.
C. Use a smaller dtype for the image array.
D. Use in-place operations for flipping and cropping.

Solution

  1. Step 1: Identify memory inefficiencies

    Intermediate assignments create unnecessary copies.

  2. Step 2: Evaluate optimization strategies

    Chaining operations reduces memory usage by avoiding intermediate arrays.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Chain operations to reduce memory usage. [OK]
Hint: Chain operations to reduce memory usage. [OK]
Common Mistakes:
4. How can you optimize a KD-Tree implementation for a KNN classifier to handle large datasets more efficiently?
hard
A. Increase the number of dimensions.
B. Use approximate nearest neighbors.
C. Use a balanced KD-Tree.
D. Reduce the number of data points.

Solution

  1. Step 1: Identify optimization strategies

    Approximate nearest neighbors can significantly speed up queries in large datasets.

  2. Step 2: Evaluate other options

    A: Balancing helps but isn't enough for large datasets. B: Increasing dimensions worsens performance. D: Reducing data points isn't always feasible.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Approximate neighbors speed up KD-Tree [OK]
Hint: Approximate neighbors speed up KD-Tree [OK]
Common Mistakes:
5. How can the calculation of precision, recall, and F1-score be optimized for a large confusion matrix?
hard
A. Use a more efficient data structure than a matrix.
B. Pre-compute and store results for common confusion matrices.
C. Use parallel processing to compute metrics for each class.
D. Approximate metrics using a subset of the data.

Solution

  1. Step 1: Identify bottlenecks

    Calculating metrics for each class can be parallelized.

  2. Step 2: Choose the best optimization strategy

    Parallel processing allows simultaneous computation, reducing time complexity.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Parallelize class-wise computations. [OK]
Hint: Parallelize class-wise computations. [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