Machine Learning · Loss Functions · Triplet Loss · Part 3 of 4

Triplet Mining and Batch Construction

July 2026 · 18 min read

A dataset can contain far more triplets than training can process. Most random triplets quickly become easy and produce zero loss. Triplet mining decides which comparisons carry useful information.

This choice changes the effective objective. A model trained with random negatives, hardest negatives, and semi-hard negatives can follow very different optimization paths even when the loss formula is identical.

Hard, Semi-Hard, and Easy Negatives

For one anchor-positive pair, write $d_{ap}=d(a,p)$ and $d_{an}=d(a,n)$.

Negative type	Distance condition	Meaning
Hard	$d_{an}<d_{ap}$	The negative is closer to the anchor than the positive
Semi-hard	$d_{ap}<d_{an}<d_{ap}+\alpha$	The ordering is correct, but the margin is still violated
Easy	$d_{an}\ge d_{ap}+\alpha$	The ordering and margin are already satisfied

A hard positive is the same-class example farthest from the anchor. It can reveal large within-class variation, but it can also be an outlier or labeling error.

▶ Mining from Five Candidate Negatives

The positive distance is $1.0$ and the margin is $0.5$. The animation classifies every candidate, then shows semi-hard and batch-hard selection.

Offline and Online Mining

Offline mining embeds a large dataset periodically and selects triplets outside the training step. It can search broadly but becomes stale as the model changes.
Online mining selects triplets from the current mini-batch. It follows the current model and is easy to vectorize, but its candidate quality depends on batch composition.

A memory bank or cross-batch queue sits between these choices. It offers more negatives than one batch, but stored embeddings were produced by older model parameters.

P by K Batches

A random batch may contain only one example from an identity, leaving no valid positive for that anchor. A structured $P\times K$ batch contains $P$ labels and $K$ examples per label:

$$B=PK.$$

Each anchor then has $K-1$ in-batch positives and $B-K$ in-batch negatives. The number of ordered valid triplets is

$$B(K-1)(B-K).$$

For $P=8$ and $K=4$, the batch has $B=32$ embeddings and

$$32\cdot3\cdot28=2688$$

valid ordered triplets before easy examples are removed. Larger $P$ gives more negative identities. Larger $K$ gives more positive variation. The choice is constrained by memory and by which side of the task needs more diversity.

Batch-All, Batch-Hard, and Semi-Hard

Strategy	Selection	Strength	Main risk
Batch-all	All valid active triplets in the batch	Uses many constraints and averages noise	Easy or repetitive triplets can dominate counts
Batch-hard	Farthest positive and nearest negative for each anchor	Strong signal with one triplet per anchor	Label noise and outliers receive maximum influence
Semi-hard	A negative farther than the positive but inside the margin	Maintains correct ordering while improving separation	Useful candidates may not exist in a small batch
Top-$k$ or distance-weighted	A controlled set or distribution of informative negatives	Balances diversity and difficulty	Adds sampling choices that also need validation

Batch-hard is often unstable at the beginning because the current embedding has not learned meaningful neighborhoods. A warm-up with random or semi-hard negatives can provide a smoother curriculum.

Vectorized Pairwise Distances

For embedding matrix $E\in\mathbb{R}^{B\times d}$, squared distances can be computed without a loop over pairs. If $s_i=\lVert E_i\rVert_2^2$, then

$$D=s\mathbf{1}^\top-2EE^\top+\mathbf{1}s^\top.$$

Floating-point cancellation can produce tiny negative entries, so squared distances are clamped at zero after the matrix expression. The diagonal is also forced to zero.

Label equality creates masks:

$$M^+_{ij}=\mathbf{1}(y_i=y_j)\mathbf{1}(i\ne j),\qquad M^-_{ij}=\mathbf{1}(y_i\ne y_j).$$

For batch-hard mining, row $i$ uses the largest $D_{ij}$ allowed by $M^+$ and the smallest $D_{ij}$ allowed by $M^-$. Invalid entries receive masked values that cannot win the corresponding reduction.

pairwise_squared(E):
    squared_norms = row_sum(E * E)
    D = squared_norms[:, None] - 2 * E * transpose(E)
        + squared_norms[None, :]
    return maximum(D, 0)

batch_hard(D, labels):
    positive_mask = same_label(labels) and not_diagonal
    negative_mask = different_label(labels)
    hardest_positive = masked_row_max(D, positive_mask)
    hardest_negative = masked_row_min(D, negative_mask)
    return mean(relu(hardest_positive - hardest_negative + margin))

Averaging the Loss Correctly

Batch-all loss is usually averaged over active triplets rather than over every combinatorial triplet:

$$L_{\text{batch-all}}= \frac{\sum_{(a,p,n)}\mathbf{1}(L_{apn}>0)L_{apn}} {\max\left(1,\sum_{(a,p,n)}\mathbf{1}(L_{apn}>0)\right)}.$$

Averaging over all triplets can make the reported loss tiny simply because the batch contains many easy zeros. The active count must be reported beside the average.

Why the Hardest Example Can Be Wrong

The nearest labeled negative may be a false negative: two semantically matching items can carry different administrative labels. The farthest positive may be a damaged sample, unusual view, or mislabeled row. Hardest-only mining gives these cases the largest gradients.

Mining amplifies label quality. Strong mining does not merely find useful signal. It also finds annotation mistakes faster than random sampling.

Common safeguards include top-$k$ sampling, capped losses, label cleanup, per-class distance inspection, and a curriculum that increases mining difficulty only after neighborhoods become meaningful.

Distributed Batches

Multi-device training can mine only within each local batch or across embeddings gathered from all devices. Global mining increases candidate diversity but also changes communication cost and gradient behavior.

If gathered remote embeddings are detached, local anchors receive gradients through local comparisons while remote examples do not receive the symmetric update from that device. A gradient-preserving all-gather gives the full objective but costs more memory and communication. The chosen behavior is part of the algorithm and must be documented.

Mining Diagnostics

Active-triplet fraction by batch and over training time
Mean and quantiles of $d_{ap}$ and $d_{an}$
Fraction of hard, semi-hard, and easy negatives
Number of valid positives and negatives per anchor
Identity or class frequency in each batch
Rate of repeated mined examples and suspected false negatives

A falling active fraction can indicate successful separation or a sampler that has stopped presenting informative comparisons. Retrieval validation distinguishes those cases.