Hard negative mining

Overview

A hard negative is a non-matching example that lies close to the anchor, usually under the current model's similarity. The three training variants below differ in where the selection happens. MinkLoc3D selects inside the loss, among the items of a batch 2011.04530 §3.2. Sample4Geo selects in the sampler, deciding which items share a batch 2303.11851 §3.3 2303.11851 §3.4. Localizing Visual Sounds the Hard Way selects inside the loss, among the locations of one frame, using soft thresholds on a similarity map 2104.02691 §3.4. All three use the model's own similarities to decide what counts as hard, and none uses a fixed set of mined negatives. A fourth variant builds hard distractors once, for ranked evaluation, from question similarity rather than from a trained model. It is not used in training 1901.09107 §4.

Two choices sit under every variant: the distance or similarity used to rank candidates, and the rule that separates a positive from a negative. MinkLoc3D uses Euclidean distance and a fixed radius, with positives within 10 m and negatives beyond 50 m. Clouds in between are ignored 2011.04530 §4.1. Sample4Geo uses cosine similarity to rank candidates 2303.11851 §3.4, and its positive is the matched pair, so it needs no threshold 2303.11851 §3.1. The soft-threshold method uses cosine similarity 2104.02691 §3.2 and two thresholds with an ignored band between them 2104.02691 §3.4.

Variants

Batch-hard mining inside each batch

Batches are built from pairs of similar clouds, so a batch of size n holds n/2 pairs 2011.04530 §3.2. For each anchor, the hardest positive is the farthest similar cloud in the batch, and the hardest negative is the closest dissimilar one. The triplet hinge uses Euclidean distance and margin 0.2 2011.04530 §3.2 2011.04530 tab. 3. The batch size starts at 32 for baseline training in Table 3, and is multiplied by 1.4 after any epoch in which less than 70% of triplets still have non-zero loss. It is capped at 256 2011.04530 tab. 3 2011.04530 §3.2. The paper also says that large batches can collapse 2011.04530 §3.2. Card: MinkLoc3D: Point Cloud Based Large-Scale Place Recognition.

The reported result is 97.9 AR@1% on Oxford with baseline training 2011.04530 tab. 4. The paper's ablations vary the aggregation layer and the descriptor size, not the mining rule 2011.04530 tab. 7 2011.04530 tab. 8, so these numbers do not isolate the effect of hard-negative mining.

GPS-neighbour batches, then similarity-based sampling

Sample4Geo trains with a symmetric InfoNCE loss over a batch of 128 2303.11851 §3.1 2303.11851 §4.2. Hard negatives enter through the batch contents, in two stages.

In the early epochs, training locations that are geographically close are put in the same batch, using their coordinates. The paper says this gives a first set of hard-ish negatives before the model has learned anything 2303.11851 §3.3.

In the later epochs, Dynamic Similarity Sampling (DSS) takes over. Every e = 4 epochs, a full inference pass over the training data gives the cosine similarities between all samples. For each query, the top K = 128 most similar samples are kept. From these, the first k/2 by similarity and k/2 drawn at random from the rest are selected, with k = 64 2303.11851 §3.4. The paper reports no collapse with DSS, even when k equals K, and presents this as an observation rather than a guarantee 2303.11851 §3.4. Card: Sample4Geo: Hard Negative Sampling For Cross-View Geo-Localisation.

Not stated in the paper: the epoch at which GPS sampling switches to DSS 2303.11851 §3.4, how the selected candidates fill batches of 128 2303.11851 §3.4, and how the two directions of the InfoNCE loss are combined 2303.11851 §3.1. The paper uses GPS sampling for CVUSA and CVACT. For University-1652, where coordinates cannot be used, it uses plain shuffling 2303.11851 §3.3.

Soft-threshold background negatives in the same frame

Localizing Visual Sounds the Hard Way has no labelled sound regions, so it takes its negatives from the same frame as the positive. The cosine map between a clip's audio and each location of its own frame is thresholded. Locations above ε_p = 0.65 get positive weight, locations below ε_n = 0.4 get negative weight, and locations between the two get no weight 2104.02691 §3.4 2104.02691 §5.3. The hard negative score is the weighted mean over the background locations 2104.02691 §3.4. The paper chose these two values by ablation 2104.02691 tab. 4. Card: Localizing Visual Sounds the Hard Way.

In that ablation, models are trained on VGG-Sound 144k and tested on Flickr SoundNet. The row with both thresholds and the band reaches cIoU 0.719, against 0.675 with no negatives 2104.02691 tab. 4. Row b uses a negative threshold of 0.6 without the band, and it scores 0.667 cIoU and 0.544 AUC, below row a's 0.675 and 0.568 2104.02691 tab. 4. The ablation varies only the thresholds and the band. It does not compare against batch-hard mining 2104.02691 tab. 4. All numbers are author-reported.

Question-similarity distractors for ranked evaluation

This variant is for testing, not training. The AVSD dialog benchmark ranks 100 candidate answers for each test question. The candidates are the true answers to the 50 training questions nearest to the query, the 30 most frequent answers in the dataset, the answers to 19 random questions, and the true answer 1901.09107 §4. Nearness is the Euclidean distance between question vectors, built from word vectors, not from a trained embedding 1901.09107 §4. The positive is the true answer, so no threshold is used. Card: Audio-Visual Scene-Aware Dialog.

The paper does not ablate this choice. Its results tables vary the input features, the dialog order and the question subsets 1901.09107 tab. 3 1901.09107 tab. 4 1901.09107 tab. 5. The best test MRR, 53.41 with dialog history and video, is therefore a score on this candidate set, and the paper does not show how it would change with another set 1901.09107 tab. 3. The repository's default composition differs from the paper's, and the candidate files it would need are not included, so the exact test candidates cannot be rebuilt from it Audio-Visual Scene-Aware Dialog.

When to use which

Implementation sketch

The first two pieces are batch-hard selection inside one batch, and DSS candidate selection for one epoch. The soft-threshold variant keeps the cosine map but replaces the mining step with per-location weights as described above; its card gives the loss in pseudocode 2104.02691 §3.4. The distractor variant builds a fixed candidate list per query, and its card gives that construction in pseudocode 1901.09107 §4.

# Batch-hard triplet selection inside one batch  [arxiv:2011.04530 §3.2]
# Input:  emb (n, D), label (n,); a positive shares the anchor's label
# Output: one hinge value per anchor that has a positive and a negative

def batch_hard_hinge(emb, label, margin=0.2):
    # Pairwise Euclidean distances, shape (n, n)  [arxiv:2011.04530 §3.2]
    dist = pairwise_l2(emb)
    same = label[:, None] == label[None, :]
    # Hardest positive: farthest item with the same label, not the anchor
    d_ap = max_where(dist, same & not_self)
    # Hardest negative: closest item with a different label
    d_an = min_where(dist, not same)
    # Hinge per anchor, margin m  [arxiv:2011.04530 §3.2]
    return relu(d_ap - d_an + margin)

# Dynamic Similarity Sampling for one epoch  [arxiv:2303.11851 §3.4]
# Input:  train_emb (N, D); k = 64 kept per query, K = 128 in the pool
# Output: chosen[q] = k training indices for each query q

def dss_candidates(train_emb, k=64, K=128):
    # Full inference pass; recomputed only every e = 4 epochs  [§3.4]
    sims = cosine_matrix(train_emb)
    for q in range(N):
        # Top K most similar items to q, most similar first  [§3.4]
        pool = top_k_indices(sims[q], K)
        # First k/2 by similarity, then k/2 drawn at random from the rest  [§3.4]
        chosen[q] = pool[: k // 2] + sample(pool[k // 2 :], k // 2)
    # Packing into batches and de-duplication within an epoch are not stated [§3.4]
    return chosen

Contradictions

• Triplet loss and collapse. Sample4Geo states that hard negatives with triplet loss can make a model collapse 2303.11851 §1 2303.11851 §3. Its triplet run on CVUSA reached R@1 0.00, with margin and mining not stated 2303.11851 supp. "Loss comparison". MinkLoc3D trains a batch-hard triplet loss and reports AR@1% 97.9 on Oxford 2011.04530 §3.2 2011.04530 tab. 4. The tasks, data and triplet setups differ, and neither paper runs the other's setup.
• Starting batch size. MinkLoc3D's Table 3 gives an initial batch size of 32 for baseline training, while the text of §3.2 says "say 16" 2011.04530 tab. 3 2011.04530 §3.2.

Papers

• Audio-Visual Scene-Aware Dialog: question-similarity distractors, with popular and random answers, for ranking 100 candidate answers in a dialog benchmark.
• MinkLoc3D: Point Cloud Based Large-Scale Place Recognition: batch-hard triplet mining, with a batch size that grows during training, for LiDAR place recognition.
• Localizing Visual Sounds the Hard Way: same-frame background negatives chosen by soft thresholds on a cosine map, with an ignored band, for self-supervised audio-visual localization.
• Sample4Geo: Hard Negative Sampling For Cross-View Geo-Localisation: GPS-neighbour batches, then Dynamic Similarity Sampling, trained with symmetric InfoNCE.