cv-lap-hard-negative-mining
Use linear assignment problem (LAP/lapjv) on a score matrix to select globally optimal hard-negative pairs for metric learning
SKILL.mdskills/cv/lap-hard-negative-mining/SKILL.md
GitHubLAP Hard Negative Mining
Overview
In metric learning, hard negatives (close but different-class examples) drive the most learning. Random negatives are too easy; per-anchor hardest negatives cause collapse. LAP (linear assignment problem) via the Jonker-Volgenant algorithm finds a globally optimal one-to-one assignment that maximizes overall difficulty across the entire batch, avoiding degenerate pairings.
Quick Start
import numpy as np
from lap import lapjv
def mine_hard_negatives(score_matrix, labels, t2i):
cost = -score_matrix.copy()
# Block same-class pairs with high cost
for cls_indices in labels.values():
idxs = [t2i[t] for t in cls_indices]
for i in idxs:
for j in idxs:
cost[i, j] = 10000.0
_, _, col_assignment = lapjv(cost)
hard_pairs = []
for j, i in enumerate(col_assignment):
hard_pairs.append((i, j))
cost[i, j] = 10000.0
cost[j, i] = 10000.0
return hard_pairs
Workflow
- Compute pairwise similarity/score matrix from current embeddings
- Mask same-class pairs with large cost to prevent them being selected
- Run
lapjvto find optimal one-to-one hard negative assignment - Use assigned pairs for contrastive/siamese training
- Recompute assignments periodically as embeddings evolve
Key Decisions
- LAP vs random: LAP finds globally hard negatives; random wastes training on easy pairs
- LAP vs per-anchor hardest: per-anchor can cause model collapse; LAP distributes difficulty
- Recompute frequency: every epoch or every N batches — stale assignments degrade quality
lappackage:pip install lapfor fast C++ Jonker-Volgenant solver