Hard Negative Mining in a Contrastive Batch
Problem Statement
Not all negatives are equal: the ones that hurt are the off-diagonal texts scoring close to or above the true match. For each image, find its hardest negative and flag the images whose hardest negative beats the positive by more than a margin — the ones the model is actively getting wrong.
Background
Given the N x N similarity matrix sim (row = image, col = text), for image i:
- the positive score is sim[i][i];
- the hardest negative is max_{j != i} sim[i][j], with ties broken by the smallest column index;
- image i is a violation when hardest_negative - positive > margin.
Your Task
Implement:
def hard_negatives(sim, margin):
Return a dict:
- "hardest_idx": list where entry i is the column index of image i's hardest negative.
- "violations": sorted list of image indices that violate the margin.
- "mean_gap": mean of (positive - hardest_negative) over all images, rounded to 4 decimals.
For N == 1 there are no negatives: hardest_idx = [-1], violations = [], mean_gap = 0.0.
Input Format
- sim: N x N nested list.
- margin (float).
Output Format
- A dict with the three keys above.
Sample
print(hard_negatives([[0.9, 0.8], [0.1, 0.7]], 0.0))
Output:
{'hardest_idx': [1, 0], 'violations': [], 'mean_gap': 0.35}
Example:
print(hard_negatives([[0.9, 0.8], [0.1, 0.7]], 0.0))
{'hardest_idx': [1, 0], 'violations': [], 'mean_gap': 0.35}Image 0: pos 0.9, hardest neg 0.8 (col1), gap 0.1. Image 1: pos 0.7, hardest neg 0.1 (col0), gap 0.6. Neither violates margin 0; mean gap (0.1+0.6)/2 = 0.35.
Constraints:
1 <= N <= 1000.- Hardest negative excludes the diagonal; ties go to the smallest column index.
- A violation is
hardest_negative - positive > margin(strict). N == 1is the documented special case.
1. Background Knowledge
Hard Negative Mining (HNM) is a core technique in contrastive learning. In a standard InfoNCE or CLIP-style batch, the loss for image i is computed against N−1 negatives. Most negatives are "easy" (low similarity), contributing little gradient signal. The hardest negative is the off-diagonal text jî€ =i with the highest similarity score sim[i][j]. If this score exceeds the positive score sim[i][i], the model is actively misranking the pair, which is a critical failure mode.
The margin concept introduces a tolerance threshold. A violation occurs when hardest_negative−positive>margin. This is analogous to the hinge loss in SVMs: we only care about errors that exceed a certain boundary. In practice, HNM is used to re-weight or select samples for the next training step, focusing capacity on the most confusing examples.
Tie-breaking is a subtle but important detail. When multiple negatives share the maximum score, we select the smallest column index. This ensures deterministic behavior, which is crucial for reproducibility in training pipelines and debugging.
2. Algorithm Approach
This is a row-wise reduction problem with a specific exclusion constraint. For each row i of the N×N matrix:
- Exclude the diagonal: The positive pair (i,i) must be ignored when searching for the hardest negative.
- Find the maximum: Scan the remaining N−1 elements in row i to find the maximum value.
- Track the index: Record the column index j where this maximum occurs, using the smallest index in case of ties.
- Evaluate the margin: Compare the found maximum against the diagonal value sim[i][i] to determine if a violation exists.
- Aggregate: Collect the indices, violation flags, and compute the mean gap across all rows.
The pattern is essentially a constrained argmax per row, followed by simple arithmetic aggregation.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.