Hard negative mining

Hard negative mining, also referred to as hard negative sampling, is a family of techniques in machine learning for selecting or constructing negative samples more difficult to distinguish from a corresponding positive example with respect to uniformly-sampled negatives, leading to a more informative training signal for discriminative classifiers and similarity models. The technique is used when the pool of possible negative examples is far larger than the set of positives and most randomly chosen negatives are easy to classify by the model, contributing little to learning. Concentrating training on the small fraction of difficult negatives is intended to provide stronger gradient signal and faster convergence than uniform sampling. Hard negative mining originated in object detection in the 1990s, where it was referred to as bootstrapping (not to be confused with statistical bootstrap resampling), and was later formalized for support vector machine models. Closely related ideas appear in deep metric learning, information retrieval, recommender systems, self-supervised contrastive learning, and vision-language models. Surveys distinguish hard negative mining from the broader practice of negative sampling, in which negatives are drawn at random or in proportion to frequency rather than by difficulty.

Background In many learning problems the number of negative examples vastly exceeds the number of positives. In sliding-window object detection, a single image yields on the order of 105 candidate windows, almost all of which are background. Online hard example mining work reports that the imbalance can reach roughly 100,000 background regions per object for sliding-window detectors and remain about 70:1 even for proposal-based detectors. Using all negative examples is both computationally infeasible and statistically harmful, because the large number of easy negatives dominates the loss and gradient. A parallel motivation arises in similarity learning. When training examples are grouped into pairs or triplets, the number of candidate tuples grows quadratically or cubically with the number of images, and once a model has converged most such tuples already satisfy the training objective and produce little or no gradient. In high-dimensional embedding spaces, randomly drawn negatives also tend to be uninformative because a significant percentage of them might already be distant from positive samples in the latent space. Selecting the most informative ("hard") examples is therefore presented as a way to keep the training signal steadier and informative throughout the whole training process.

Definition and terminology Across application areas, a hard negative is consistently defined relative to the model being trained: it is a negative (an example whose label differs from that of the anchor or query), that the current model nonetheless classifies as a positive. For instance, in a margin-based detector, like a SVM a hard negative is a background example that is misclassified or that falls within the classifier's margin. In embedding-based methods, it is a differently-labelled example that lies close to the anchor in the learned feature space. Several finer distinctions are commonly utilized:

Hard, semi-hard and easy negatives. In triplet loss training, a hard negative is the differently-labelled example closest to the anchor; an easy negative is the most distant one (and gives little useful gradient); and a semi-hard negative is one that is farther from the anchor than the matching positive yet still inside the loss margin. The term semi-hard was introduced in the FaceNet system. Hardness relative to model capacity. Whether an example counts as hard depends on the model complexity: a high-complexity model treats most examples as easy, while a low-complexity model treats most as hard. Hard negative mining versus hard example mining. Some authors generalize the term preferring hard example mining to extend this techniques to also focus on positive samples that the model finds harder to classify correctly.

Techniques

Object detection In classical detectors, hard negative mining is an iterative, cache-based procedure layered on top of an SVM or other classifier: the model is trained on the positives and a small set of negatives, the trained model is run over background data to collect new false positives, easy examples are discarded, and the model is retrained, repeating a few times. A negative is treated as hard when its margin score indicates misclassification or a within-margin position. Online hard example mining (OHEM) adapts this idea to the training of deep region-based detectors. Rather than alternating offline mining and retraining, OHEM forms each SGD mini-batch by scoring all candidate regions of interest with a read-only forward pass, and then back-propagating only through the highest-loss regions. An efficient implementation keeps two copies of the region network: one read-only copy that scores all regions and one trainable copy that processes only the selected hard examples. Hard negative mining has likewise been applied to convolutional face detectors by harvesting false positives from a first-round Faster R-CNN face detector and retraining on them, labelling a detected region a hard negative when its maximum intersection-over-union with any ground-truth face falls below a certain treshold.

Deep metric learning

… excerpt ends here. Continue reading the full article.