Understanding Hard Negatives in Noise Contrastive Estimation (2021)

Abstract: The choice of negative examples is important in noise contrastive estimation. Recent works find that hard negatives—highest-scoring incorrect examples under the model—are effective in practice, but they are used without a formal justification. We develop analytical tools to understand the role of hard negatives. Specifically, we view the contrastive loss as a biased estimator of the gradient of the cross-entropy loss, and show both theoretically and empirically that setting the negative distribution to be the model distribution results in bias reduction. We also derive a general form of the score function that unifies various architectures used in text retrieval. By combining hard negatives with appropriate score functions, we obtain strong results on the challenging task of zero-shot entity linking.

## introduction noise contrastive estimation (nce) is a widely used approach to large-scale classification and retrieval. it estimates a score function of inputlabel pairs by a sampled softmax objective: given a correct pair (x, y 1 ), choose negative examples y 2 . . . y k and maximize the probability of (x, y 1 ) in a softmax over the scores of (x, y 1 ) . . . (x, y k ). nce has been successful in many applications, including information retrieval @xcite , entity linking @xcite , and opendomain question answering @xcite . it is well known that making negatives "hard" can be empirically beneficial. for example, @xcite propose a hard negative mining strategy in which highest-scoring incorrect labels under the current model are chosen as negatives. some works even manually include difficult examples based on external information such as a ranking function @xcite or a knowledge base @xcite . while it is intuitive that such hard negatives help improve the final model by making the learning task more challenging, they are often used without a formal justification. existing theoretical results in contrastive learning are not suitable for understanding hard negatives since they focus on unconditional negative distributions @xcite @xcite or consider a modified loss divergent from practice @xcite . in this work, we develop analytical tools to understand the role of hard negatives. we formalize hard-negative nce with a realistic loss (5) using a general conditional negative distribution, and view it as a biased estimator of the gradient of the crossentropy loss. we give a simple analysis of the bias (theorem 3.1). we then consider setting the negative distribution to be the model distribution, which recovers the hard negative mining strategy of @xcite , and show that it yields an unbiased gradient estimator when the model is optimal (theorem 3.2). we complement the gradient-based perspective with an adversarial formulation (theorem 3.3). the choice of architecture to parametrize the score function is another key element in nce. there is a surge of interest in developing efficient cross-attentional architectures @xcite @xcite , but they often address different tasks and lack direct comparisons. we give a single algebraic form of the score function (9) that subsumes and generalizes these works, and directly compare a spectrum of architectures it induces. we present experiments on the challenging task of zero-shot entity linking @xcite . we calculate empirical estimates of the bias of the gradient estimator to verify our analysis, and systematically explore the joint space of negative examples and architectures. we have clear practical recommendations: (i) hard negative mining always improves performance for all architectures, and (ii) the sum-of-max encoder @xcite ) yields the best recall in entity retrieval. our final model combines the sum-ofmax retriever with a bert-based joint reranker to achieve 67.1% unnormalized accuracy: a 4.1% absolute improvement over @xcite . we also present complementary experiments on aida conll-yago @xcite in which we finetune a wikipedia-pretrained dual encoder with hard-negative nce and show a 6% absolute improvement in accuracy. ## review of nce let x and y denote input and label spaces. we assume |y| < ∞ for simplicity. let pop denote a joint population distribution over x × y. we define a score function s θ : x × @xmath0. given sampling access to pop, we wish to estimate θ such that the classifier @xmath1, y) (breaking ties arbitrarily) has the optimal expected zero-one loss. we can reduce the problem to conditional density estimation. given @xmath2, define for all @xmath3. let θ * denote a minimizer of the cross-entropy loss: if the score function is sufficiently expressive, θ * satisfies p θ * (y|x) = pop(y|x) by the usual property of cross entropy. this implies that s θ * can be used as an optimal classifier. the cross-entropy loss is difficult to optimize when y is large since the normalization term in (1) is expensive to calculate. in nce, we dodge this difficulty by subsampling. given @xmath4 for all 1 ≤ @xmath5. when k |y|, (3) is significantly cheaper to calculate than (1). given @xmath6, we define the nce loss (4) has been studied extensively. an optimal classifier can be extracted from a minimizer of j nce @xcite ; minimizing j nce can be seen as maximizing a lower bound on the mutual information between (x, y) ∼ pop if q is the population marginal @xcite . we refer to @xcite for an overview. however, most of these results focus on unconditional negative examples and do not address hard negatives, which are clearly conditional. we now focus on conditional negative distributions, which are more suitable for describing hard negatives. ## hard negatives in nce we give two interpretations of optimizing j hard . first, we show that the gradient of j hard is a biased estimator of the gradient of the cross-entropy loss j ce . thus optimizing j hard approximates optimizing j ce when we use a gradient-based method, where the error depends on the choice of h(•|x, y 1 ). second, we show that the hard negative mining strategy can be recovered by considering an adversarial setting in which h(•|x, y 1 ) is learned to maximize the loss. ## score function along with the choice of negatives, the choice of the score function s θ : x ×@xmath7. there is a clear tradeoff between performance and efficiency in modeling the cross interaction between the input-label pair (x, y). this trade-off spurred many recent works to propose various architectures in search of a sweet spot @xcite ), but they are developed in isolation of one another and difficult to compare. in this section, we give a general algebraic form of the score function that subsumes many of the existing works as special cases. ## related work we discuss related work to better contextualize our contributions. there is a body of work on developing unbiased estimators of the population distribution by modifying nce. the modifications include learning the normalization term as a model parameter @xcite and using a bias-corrected score function @xcite . however, they assume unconditional negative distributions and do not explain the benefit of hard negatives in nce @xcite @xcite . in contrast, we directly consider the hard-negative nce loss used in practice (5), and justify it as a biased estimator of the gradient of the cross-entropy loss. our work is closely related to prior works on estimating the gradient of the cross-entropy loss, again by modifying nce. they assume the following loss @xcite , which we will denote by j prior (θ): here, ν(•|x, y 1 ) is a conditional distribution over y\ {y 1 }, and sθ (x, y , y) is equal to s θ (x, y) if @xmath8, y) -log((k -1)ν(y|x, y 1 )) otherwise. it can be shown that ∇j prior (θ) = ∇j ce (θ) iff ν(y|x, y 1 ) ∝ exp(s θ (x, y)) for all @xmath9. however, (10) requires adjusting the score function and iid negative examples, thus less aligned with practice than (5). the bias analysis of ∇j prior (θ) for general ν(•|x, y 1 ) is also significantly more complicated than theorem 3.1 @xcite . there is a great deal of recent work on unsupervised contrastive learning of image embeddings in computer vision @xcite @xcite , inter alia). here, s θ (x, y) = e θ (x) f θ (y) is a similarity score between images, and e θ or f θ is used to produce useful image representations for downstream tasks. the model is again learned by (4) where (x, y 1 ) are two random corruptions of the same image and y 2:k are different images. @xcite propose a hard negative distribution in this setting and analyze the behavior of learned embeddings under that distribution. in contrast, our setting is large-scale supervised classification, such as entity linking, and our analysis is concerned with nce with general hard negative distributions. in a recent work, @xcite consider contrastive learning for text retrieval with hard negatives obtained globally from the whole data with asynchronous updates, as we do in our experiments. they use the framework of importance sampling to argue that hard negatives yield gradients with larger norm, thus smaller variance and faster convergence. however, their argument does not imply our theorems. they also assume a pairwise loss, excluding non-pairwise losses such as (4). ## experiments we now study empirical aspects of the hardnegative nce (section 3) and the spectrum of score functions (section 4). our main testbed is zeshel @xcite , a challenging dataset for zero-shot entity linking. we also present complementary experiments on aida conll-yago @xcite ). foot_2 6.1 task zeshel contains 16 domains (fictional worlds like star wars) partitioned to 8 training and 4 validation and test domains. each domain has tens of thousands of entities along with their textual descriptions, which contain references to other entities in the domain and double as labeled mentions. the input x is a contextual mention and the label y is the description of the referenced entity. a score function s θ (x, y) is learned in the training domains and applied to a new domain for classification and retrieval. thus the model must read descriptions of unseen entities and still make correct predictions. we follow prior works and report microaveraged top-64 recall and macro-averaged accuracy for evaluation. the original zeshel paper @xcite distinguishes normalized vs unnormalized accuracy. normalized accuracy assumes the presence of an external retriever and considers a mention only if its gold entity is included in top-64 candidates from the retriever. in this case, the problem is reduced to reranking and a computationally expensive joint encoder can be used. unnormalized accuracy considers all mentions. our goal is to improve unnormalized accuracy. @xcite use bm25 for retrieval, which upper bounds unnormalized accuracy by its poor recall (first row of ## conclusions hard negatives can often improve nce in practice, substantially so for entity linking @xcite , but are used without justification. we have formalized the role of hard negatives in quantifying the bias of the gradient of the contrastive loss with respect to the gradient of the full cross-entropy loss. by jointly optimizing the choice of hard negatives and architectures, we have obtained new state-ofthe-art results on the challenging zeshel dataset @xcite .