The choice of negative examples is important in noise contrastive estimation. Recent works find that hard negativeshighest-scoring incorrect examples under the modelare 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. Noise contrastive estimation (NCE) is a widely used approach to large-scale classification and retrieval. It estimates a score function of input-label 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 (Huang et al., 2013), entity linking (Gillick et al., 2019), and open-domain question answering (Karpukhin et al., 2020). It is well known that making negatives hard can be empirically beneficial. For example, Gillick et al. (2019) 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 (Karpukhin et al., 2020) or a knowledge base (Fvry et al., 2020). 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 (Gutmann and Hyvri-nen, 2012; Mnih and Teh, 2012; Ma and Collins, 2018; Tian et al., 2020) or consider a modified loss divergent from practice (Bengio and Sencal, 2008). 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 cross-entropy 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 Gillick et al. (2019), 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 (Theo-rem 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 (Humeau et al., 2020; Khattab and Zaharia, 2020; Luan et al., 2020), 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 (Logeswaran et al., 2019). 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 (Khattab and Zaharia, 2020) yields the best recall in entity retrieval. Our final model combines the sum-of-max retriever with a BERT -based joint reranker to achieve 67.1% unnormalized accuracy: a 4.1% absolute improvement over Wu et al. (2020). We also present complementary experiments on AIDA CoNLL-YAGO (Hoffart et al., 2011) in which we finetune a Wikipedia-pretrained dual encoder with hard-negative NCE and show a 6% absolute improvement in accuracy. 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  Y  R differentiable in   R d . Given sampling access to pop , we wish to estimate  such that the classifier x (cid:55) arg max y Y s  ( x, y ) (breaking ties arbitrarily) has the optimal expected zero-one loss. We can reduce the problem to conditional density estimation. Given x  X , define p  ( y | x ) = exp ( s  ( x, y )) (cid:80) y (cid:48) Y exp ( s  ( x, y (cid:48) )) (1) for all y  Y . 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 x  X and any K labels y 1: K = ( y 1 . . . y K )  YK , define   ( k | x, y 1: K ) = exp ( s  ( x, y k )) (cid:80) Kk (cid:48) =1 exp ( s  ( x, y k (cid:48) )) (3) for all 1  k  K . where y 2: K  YK  1 are negative examples drawn iid from some noise distribution q over Y . Popular choices of q include the uniform distribution q ( y ) = 1 / |Y| and the population marginal q ( y ) = pop ( y ) . The NCE loss (4) has been studied extensively. An optimal classifier can be extracted from a minimizer of JNCE (Ma and Collins, 2018); minimizing JNCE can be seen as maximizing a lower bound on the mutual information between ( x, y )  pop if q is the population marginal (Oord et al., 2018). We refer to Stratos (2019) 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. Given K  2 , we define where y 2: K  YK  1 are negative examples drawn from a conditional distribution h ( | x, y 1 ) given ( x, y 1 )  pop . Note that we do not assume y 2: K are iid. While simple, this objective captures the essence of using hard negatives in NCE, since the negative examples can arbitrarily condition on the input and the gold (e.g., to be wrong but difficult to distinguish from the gold) and be correlated (e.g., to avoid duplicates). We give two interpretations of optimizing JHARD . First, we show that the gradient of JHARD is a biased estimator of the gradient of the cross-entropy loss JCE . Thus optimizing JHARD approximates optimizing JCE 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. We assume an arbitrary choice of h ( | x, y 1 ) and K  2 . Denote the bias at   R d by b (  ) =  JCE (  )   JHARD (  ) To analyze the bias, the following quantity will be important. 2: K 1 k    ( | x,y 1: K ) For all i = 1 . . . d , b i (  ) = E x  pop  (cid:88) y Y (cid:15)  ( y | x ) s  ( x, y )  i   where (cid:15)  ( y | x ) = p  ( y | x )    ( y | x ) . Proof. Fix any x  X and let J x CE (  ) and J x HARD (  ) denote JCE (  ) and JHARD (  ) conditioned on x . The difference J x CE (  )  J x HARD (  ) is log Z  ( x )  E y 1  pop ( | x ) y 2: K  h ( | x,y 1 ) [log Z  ( x, y 1: K )] (7) where we define Z  ( x ) = (cid:80) y (cid:48) Y exp ( s  ( x, y (cid:48) )) and Z  ( x, y 1: K ) = (cid:80) Kk =1 exp( s  ( x, y k )) . The statement follows from the chain rule: b i (  ) = (cid:88) x X ,y Y b (  ) s  ( x, y ) s  ( x, y )  i Theorem 3.1 states that the bias vanishes if   ( y | x ) matches p  ( y | x ) . for all y  Y . That is,   ( y | x ) is the probability that y is included as a candidate (either as the gold or a negative) and then selected by the NCE discriminator (3). Theorem 3.1. For any ( x,  y ) , the partial derivative of (7) with respect to s  ( x,  y ) is given by [[ x =  x ]] p  ( y | x )  [[ x =  x ]]   ( y | x ) where [[ A ]] is the indicator function that takes the value 1 if A is true and 0 otherwise. Taking an expectation of their difference over x  pop gives the partial derivative of b (  ) = JCE (  )  JHARD (  ) with respect to s  ( x,  y ) : pop ( x )( p  ( y |  x )    ( y |  x )) . Hard negative mining can be seen as an attempt to minimize the bias by defining h ( | x, y 1 ) in terms of p  . Specifically, we define h ( y 2: K | x, y 1 )  [[ |{ y 1 . . . y K }| = K ]] K (cid:89) k =2 p  ( y k | x ) (8) Thus h ( | x, y 1 ) has support only on y 2: K  YK  1 that are distinct and do not contain the gold. sampling from h ( | x, y 1 ) corresponds to taking K  1 incorrect label types with highest scores. This coincides with the hard negative mining strategy of Gillick et al. (2019). The absence of duplicates in y 1: K ensures JCE (  ) = JHARD (  ) if K = |Y| . This is consistent with (but does not imply) Theorem 3.1 since in this case   ( y | x ) = p  ( y | x ) . For general K < |Y| , Theorem 3.1 still gives a precise bias term. To gain a better insight into its behavior, it is helpful to consider a heuristic approximation given by 1   ( y | x )  p  ( y | x ) exp ( s  ( x, y )) N  ( x ) where N  ( x ) = (cid:80) y (cid:48) Y p  ( y (cid:48) | x ) exp ( s  ( x, y (cid:48) )) . where   ( x, y ) = exp ( s  ( x, y )) /N  ( x ) . The expression suggests that the bias becomes smaller as the model improves since p  ( | x )  pop ( | x ) implies   ( x, y )  1 where ( x, y )  pop . We can formalize the heuristic argument to prove a desirable property of (5): the gradient is unbiased if  satisfies p  ( y | x ) = pop ( y | x ) , assuming iid hard negatives. Theorem 3.2. Assume K  2 and the distribution h ( y 2: K | x, y 1 ) = (cid:81) Kk =2 p  ( y k | x ) in (5). If p  ( y | x ) = pop ( y | x ) , then  JHARD (  ) =  JCE (  ) . Proof. Since pop ( y | x ) = exp( s  ( x, y )) /Z  ( x ) , the probability   ( y | x ) in (6) is (cid:88) y 1: K Y KK (cid:89) k =1 exp ( s  ( x, y k )) Z  ( x ) exp ( s  ( x, y )) Z  ( x, y 1: K ) = exp ( s  ( x, y )) Z  ( x ) (cid:88) y 1: K Y K (cid:81) Kk =1 exp ( s  ( x, y k )) Z  ( x, y 1: K ) The sum marginalizes a product distribution over y 1: K , thus equals one. Hence   ( y | x ) = p  ( y | x ) . The statement follows from Theorem 3.1. 1 We can rewrite   ( y | x ) as E y 1  pop ( | x ) y 2: K  h ( | x,y 1 ) (cid:34) count y 1: K ( y ) exp ( s  ( x, y )) (cid:80) y (cid:48) Y count y 1: K ( y (cid:48) ) exp ( s  ( x, y (cid:48) )) (cid:35) where count y 1: K ( y ) is the number of times y appears in y 1: K . The proof exploits the fact that negative examples are drawn from the model and does not generally hold for other negative distributions (e.g., uniformly random). We empirically verify that hard negatives indeed yield a drastically smaller bias compared to random negatives (Section 6.4). We complement the bias-based view of hard negatives with an adversarial view. We generalize (5) and define JADV ( , h ) = E ( x,y 1 )  pop y 2: K  h ( | x,y 1 ) [  log   (1 | x, y 1: K )] where we additionally consider the choice of a hard-negative distribution. The premise of adversarial learning is that it is beneficial for  to consider the worst-case scenario when minimizing this loss. This motivates a nested optimization problem: min   R d max h H JADV ( , h ) where H denotes the class of conditional distributions over S  Y satisfying | S  { y 1 }| = K . Theorem 3.3. Fix   R d . For any ( x, y 1 ) , pick  y 2: K  arg max y 2: K Y K  1 : |{ y 1 ...y K }| = K K (cid:88) k =2 s  ( x, y k ) breaking ties arbitrarily, and define the point-mass distribution over YK  1 :  h ( y 2: K | x, y 1 ) = [[ y k =  y k  k = 2 . . . K ]] Then  h  arg max h H JADV ( , h ) . Proof. max h H JADV ( , h ) is equivalent to max h H E ( x,y 1 )  pop y 2: K  h ( | x,y 1 ) (cid:34) log K (cid:88) k =1 exp ( s  ( x, y k )) (cid:35) The expression inside the expectation is maximized by  y 2: K by the monotonicity of log and exp , subject to the constraint that |{ y 1 . . . y K }| = K . h  H achieves this maximum. Along with the choice of negatives, the choice of the score function s  : X Y  R is a critical component of NCE in practice. 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 (Humeau et al., 2020; Luan et al., 2020), 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. We focus on the standard setting in NLP in which x  VT and y  VT (cid:48) are sequences of tokens in a vocabulary V . Let E ( x )  RH  T and F ( y )  RH  T (cid:48) denote their encodings, typically obtained from the final layers of separate pretrained transformers like BERT (Devlin et al., 2019). We follow the convention popularized by BERT and assume the first token is a special symbol (i.e., [CLS]), so that E 1 ( x ) and F 1 ( y ) represent single-vector summaries of x and y . We have the following design choices:  Direction : If x  y , define the query Q = E ( x ) and key K = F ( y ) . If y  x , define the query Q = F ( y ) and key K = E ( x ) . Reduction : Given integers m, m (cid:48) , reduce the number of columns in Q and K to obtain Q m  RH  m and K m (cid:48)  RH  m (cid:48) . We can simply select leftmost columns, or introduce an additional layer to perform the reduction. Attention : Choose a column-wise attention Attn : A (cid:55) s A either Soft or Hard . If Soft , s A t = softmax( A t ) where the subscript denotes the column index. If Hard , s A t is a vector of zeros with exactly one 1 at index arg max i [ A t ] i . Given the design choices, we define the score of ( x, y ) as s  ( x, y ) = 1 (cid:62) m Q (cid:62) m K m (cid:48) Attn (cid:16) K (cid:62) m (cid:48) Q m (cid:17) (9) where 1 m is a vector of m 1s that aggregates query scores. Note that the query embeddings Q m double as the value embeddings. The parameter vector   R d denotes the parameters of the encoders E, F and the optional reduction layer. Dual encoder. Choose either direction x  y or y  x . Select the leftmost m = m (cid:48) = 1 vectors in Q and K as the query and key. The choice of attention has no effect. This recovers the standard dual encoder used in many retrieval problems (Gupta et al., 2017; Lee et al., 2019; Logeswaran et al., 2019; Wu et al., 2020; Karpukhin et al., 2020; Guu et al., 2020): s  ( x, y ) = E 1 ( x ) (cid:62) F 1 ( y ) . Poly-encoder. Choose the direction y  x . Select the leftmost m = 1 vector in F ( y ) as the query. Choose an integer m (cid:48) and compute K m (cid:48) = E ( x )Soft( E ( x ) (cid:62) O ) where O  RH  m (cid:48) is a learnable parameter (code embeddings). Choose soft attention. This recovers the poly-encoder (Humeau et al., 2020): s  ( x, y ) = F 1 ( y ) (cid:62) C m (cid:48) ( x, y ) where C m (cid:48) ( x, y ) = K m (cid:48) Soft (cid:0) K (cid:62) m (cid:48) F 1 ( y ) (cid:1) . Similar architectures without length reduction have been used in previous works, for instance the neural attention model of Ganea and Hofmann (2017). Sum-of-max. Choose the direction x  y . Select all m = T and m (cid:48) = T (cid:48) vectors in E ( x ) and F ( y ) as the query and key. Choose Attn = Hard . This recovers the sum-of-max encoder (aka., Col-BERT) (Khattab and Zaharia, 2020): s  ( x, y ) = (cid:80) Tt =1 max T (cid:48) t (cid:48) =1 E t ( x ) (cid:62) F t (cid:48) ( y ) . Multi-vector. Choose the direction x  y . Select the leftmost m = 1 and m (cid:48) = 8 vectors in E ( x ) and F ( y ) as the query and key. Choose Attn = Hard . This recovers the multi-vector encoder (Luan et al., 2020): s  ( x, y ) = max m (cid:48) t (cid:48) =1 E 1 ( x ) (cid:62) F t (cid:48) ( y ) . It reduces computation to fast dot products over cached embeddings, but is less expressive than the sum-of-max. The abstraction (9) is useful because it generates a spectrum of architectures as well as unifying existing ones. For instance, it is natural to ask if we can further improve the poly-encoder by using m > 1 query vectors. We explore these questions in experiments. 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 (Gutmann and Hyvrinen, 2012; Mnih and Teh, 2012) and using a bias-corrected score function (Ma and Collins, 2018). However, they assume unconditional negative distributions and do not explain the benefit of hard negatives in NCE (Gillick et al., 2019; Wu et al., 2020; Karpukhin et al., 2020; Fvry et al., 2020). 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 (Bengio and Sencal, 2008), which we will denote by JPRIOR (  ) : E ( x,y 1 )  pop y 2: K   ( | x,y 1 ) K (cid:34)  log exp ( s  ( x, y 1 , y 1 )) (cid:80) Kk =1 exp ( s  ( x, y 1 , y k )) (cid:35) (10) Here,  ( | x, y 1 ) is a conditional distribution over Y\ { y 1 } , and  s  ( x, y (cid:48) , y ) is equal to s  ( x, y ) if y = y (cid:48) and s  ( x, y )  log(( K  1)  ( y | x, y 1 )) otherwise. It can be shown that  JPRIOR (  ) =  JCE (  ) iff  ( y | x, y 1 )  exp( s  ( x, y )) for all y  Y\ { y 1 } (Blanc and Rendle, 2018). However, (10) requires adjusting the score function and iid negative examples, thus less aligned with practice than (5). The bias analysis of  JPRIOR (  ) for general  ( | x, y 1 ) is also significantly more complicated than Theorem 3.1 (Rawat et al., 2019). There is a great deal of recent work on unsupervised contrastive learning of image embeddings in computer vision (Oord et al., 2018; Hjelm et al., 2019; Chen et al., 2020, inter alia ). Here, s  ( x, y ) = E  ( x ) (cid:62) 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. Robinson et al. (2021) 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, Xiong et al. (2021) 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). We now study empirical aspects of the hard-negative NCE (Section 3) and the spectrum of score functions (Section 4). Our main testbed is Zeshel (Logeswaran et al., 2019), a challenging dataset for zero-shot entity linking. We also present complementary experiments on AIDA CoNLL-YAGO (Hoffart et al., 2011). 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 micro-averaged top-64 recall and macro-averaged accuracy for evaluation. The original Zeshel paper (Lo-geswaran et al., 2019) 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. Logeswaran et al. (2019) use BM25 for retrieval, which upper bounds unnormalized accuracy by its poor recall (first row of Table 1). Wu et al. (2020) propose a two-stage approach in which a dual encoder is trained by hard-negative NCE and held fixed, then a BERT -based joint encoder is trained to rerank the candidates retrieved by the dual encoder. This approach gives considerable improvement in unnormalized accuracy, primarily due to the better recall of a trained dual encoder over BM25 (sec-ond row of Table 1). We show that we can further push the recall by optimizing the choice of hard negatives and architectures. We represent x and y as length128 wordpiece sequences where the leftmost token is the special symbol [CLS]; we mark the boundaries of a mention span in x with special symbols. We use two independent BERT -bases to calculate mention embeddings E ( x )  R 768  128 and entity embeddings F ( y )  R 768  128 , where the columns E t ( x ) , F t ( y ) are contextual embeddings of the t -th tokens. Retriever. The retriever defines s  ( x, y ) , the score between a mention x and an entity y , by one of the architectures described in Section 4.2: E 1 ( x ) (cid:62) F 1 ( y ) ( DUAL ) F 1 ( y ) (cid:62) C m ( x, y ) ( POLYm ) max mt =1 E 1 ( x ) (cid:62) F t ( y ) ( MULTIm ) (cid:80) 128 t =1 max 128 t (cid:48) =1 E t ( x ) (cid:62) F t (cid:48) ( y ) ( SOM ) denoting the dual encoder, the poly-encoder (Humeau et al., 2020), the multi-vector encoder (Luan et al., 2020), and the sum-of-max encoder (Khattab and Zaharia, 2020). These architectures are sufficiently efficient to calculate s  ( x, y ) for all entities y in training domains for each mention x . This efficiency is necessary for sampling hard negatives during training and retrieving candidates at test time. Reranker. The reranker defines s  ( x, y ) = w (cid:62) E 1 ( x, y )+ b where E ( x, y )  RH  256 is BERT (either base H = 768 or large H = 1024 ) embeddings of the concatenation of x and y separated by the special symbol [SEP], and w, b are parameters of a linear layer. We denote this encoder by JOINT . Training a retriever. A retriever is trained by minimizing an empirical estimate of the hard-negative NCE loss (5), (cid:98) JHARD (  ) =  1 NN (cid:88) i =1 log exp ( s  ( x i , y i, 1 )) (cid:80) Kk (cid:48) =1 exp (cid:0) s  ( x i , y i,k (cid:48) ) (cid:1) (11) where ( x 1 , y 1 , 1 ) . . . ( x N , y N, 1 ) denote N mention-entity pairs in training data, and y i, 2 . . . y i,K  h ( | x i , y i, 1 ) are K  1 negative entities for the i th mention. We vary the choice of negatives as follows. Hard: The negatives are sampled from (8) each epoch. That is, in the beginning of each training pass, for each i we sample entities y i, 2 . . . y i,K from Y\ { y i, 1 } without replacement with probabilities proportional to exp ( s  ( x i , y i,k )) . This is slightly different from, and simpler than, the original hard negative mining strategy of Gillick et al. (2019) which pretrains the model using random negatives then greedily adds negative entities that score higher than the gold. Mixedp : p percent of the negatives are hard, the rest are random. Previous works have shown that such a combination of random and hard negatives can be effective. We find the performance is not sensitive to the value of p (Appendix A). We experimented with in-batch sampling as done in previous works (e.g., Gillick et al. (2019)), but found sampling from all training data to be as effective and more straightforward (e.g., the number of random negatives is explicitly unrelated to the batch size). We use K = 64 in all experiments. Training a reranker. We use JOINT only for reranking by minimizing (11) with top-63 negatives given by a fixed retriever, where we vary the choice of retriever. We also investigate other architectures for reranking such as the poly-encoder and the sum-of-max encoder, but we find the full cross attention of JOINT to be indispensable. Details of reranking experiments can be found in Appendix B. Other details. All models are trained up to 4 epochs using Adam. We tune the learning rate over { 5e  5 , 2e  5 , 1e  5 } on validation data. We use the training batch size of 4 mentions for all models Model Negatives Val Test BM 25  76.22 69.13 Wu et al. (2020) Mixed (10 hard) 91.44 82.06 DUAL Random 91.08 81.80 Hard 91.99 84.87 Mixed-50 91.75 84.16 DUAL(10) Hard 91.57 83.08 POLY16 Random 91.05 81.73 Hard 92.08 84.07 Mixed-50 92.18 84.34 MULTI8 Random 91.13 82.44 Hard 92.35 84.94 Mixed-50 92.76 84.11 SOM Random 92.51 87.62 Hard 94.49 88.68 Mixed-50 94.66 89.62 Table 1: Top-64 recalls over different choices of architecture and negative examples for a retriever trained by NCE. except for JOINT , for which we use 2 . Training time is roughly half a day on a single NVIDIA A100 GPU for all models, except the SOM retriever which takes 1-2 days. We conduct experiments on synthetic data to empirically validate our bias analysis in Section 3.1. Analogous experiments on Zeshel with similar find-ings can be found in Appendix C. We construct a population distribution over 1000 labels with small entropy to represent the peaky conditional label distribution pop ( y | x ) . We use a feedforward network with one ReLU layer to estimate this distribution by minimizing the empirical cross-entropy loss based on 128 iid samples per update. At each update, we compute cross-entropy (2) exactly, and estimate NCE (5) with 4 negative samples by Monte Carlo (10 simulations). Figure 1 plots the value of the loss function (left) and the norm of the gradient bias (right) across updates. We first observe that hard NCE yields an accurate estimate of cross entropy even with 4 samples. In contrast, random NCE quickly converges to zero, reflecting the fact that the model can trivially discriminate between the gold and random labels. We next observe that the bias of the gradient of hard NCE vanishes as the model distribution converges to the population distribution, which supports our analysis that the bias becomes smaller as the model improves. The bias remains nonzero for random NCE. Table 1 shows the top-64 recall (i.e., the percentage of mentions whose gold entity is included in the 64 entities with highest scores under a retriever trained by (5)) as we vary architectures and negative examples. We observe that hard and mixed negative examples always yield sizable improvements over random negatives, for all architectures. Our dual encoder substantially outperforms the previous dual encoder recall by Wu et al. (2020), likely due to better optimization such as global vs in-batch random negatives and the proportion of hard negatives. We also train a dual encoder with the bias-corrected loss (10) and find that this does not improve recall. The poly-encoder and the multi-vector models are comparable to but do not improve over the dual encoder. However, the sum-of-max encoder delivers a decisive improvement, especially with hard negatives, pushing the test recall to above 89%. Based on this finding, we use DUAL and SOM for retrieval in later experiments. We show our main results in Table 2. Following Wu et al. (2020), we do two-stage training in which we train a DUAL or SOM retriever with hard-negative NCE and train a JOINT reranker to rerank its top-64 candidates. All our models outperform the previous best accuracy of 63.03% by Wu et al. (2020). In fact, our dual encoder retriever using a BERT -base reranker outperforms the dual encoder retriever using a BERT -large reranker (65.42% vs 63.03%). We obtain a clear improvement by switching the retriever from dual encoder to sum-of-max due to its high recall (Table 1). Using a sum-of-max retriever trained with mixed negatives and a BERT large reranker gives the best result 67.14%. To better understand practical implications of hard negative mining, we compare a SOM retriever trained on Zeshel with random vs hard negatives (92.51 vs 94.66 in top-64 validation recall). The Model Accuracy BLINK without finetuning 80.27 BLINK with finetuning 81.54 DUAL with p = 0 82.40 DUAL with p = 50 88.01 MULTI2 with p = 50 88.39 MULTI3 with p = 50 87.94 Table 4: Test accuracies on AIDA CoNLL-YAGO. mention categories most frequently improved are Low Overlap (174 mentions) and Multiple Categories (76 mentions) (see Logeswaran et al. (2019) for the definition of these categories), indicating that hard negative mining makes the model less reliant on string matching. A typical example of improvement is shown in Table 3. The random-negative model retrieves person, device, or institution entities because they have more string overlap (e.g. Mehrunes Dagon, Battlespire, and Tharn). In contrast, the hard-negative model appears to better understand that the mention is referring to a chaotic event like the Fall of Ald'ruhn, Sack of Mournhold, and Oblivion Crisis and rely less on string matching. We hypothesize that this happens because string matching is sufficient to make a correct prediction during training if negative examples are random, but insufficient when they are hard. To examine the effect of encoder architecture, we also compare a DUAL vs SOM retriever both trained with mixed negatives (91.75 vs 94.66 in top-64 validation recall). The mention categories most frequently improved are again Low Overlap (335 mentions) and Multiple Categories (41 mentions). This indicates that cross attention likewise helps the model less dependent on simple string matching, presumably by allowing for a more expressive class of score functions. We complement our results on Zeshel with additional experiments on AIDA. We use BLINK , a Wikipedia-pretrained two-stage model (a dual encoder retriever pipelined with a joint reranker, both based on BERT ) made available by Wu et al. (2020). 3 We extract the dual encoder module from BLINK and finetune it on AIDA using the training portion. During finetuning, we use all 5.9 million Wikipedia entities as candidates to be consistent with prior work. Because of the large scale of the knowledge base we do not consider SOM and focus on the MULTIm retriever ( DUAL is a special case with m = 1 ). At test time, all models consider all Wikipedia entities as candidates. For both AIDA and the Wikipedia dump, we use the version prepared by the KILT benchmark (Petroni et al., 2020). Table 4 shows the results. Since Wu et al. (2020) do not report AIDA results, we take the performance of BLINK without and with finetuning from their GitHub repository and the KILT leaderboard. 4 We obtain substantially higher accuracy by mixed-negative training even without reranking. 5 There is no significant improvement from using m > 1 in the multi-vector encoder on this task. Hard negatives can often improve NCE in practice, substantially so for entity linking (Gillick et al., 2019), 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-of-the-art results on the challenging Zeshel dataset (Logeswaran et al., 2019). This work was supported by the Google Faculty Research Awards Program. We thank Ledell Wu for many clarifications on the BLINK paper.
abstain abstain objective result method result abstain abstain abstain abstain abstain abstain abstain abstain objective objective abstain result abstain abstain abstain method method objective abstain abstain abstain result result abstain method abstain method method method abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain method method abstain method abstain method abstain method abstain method abstain abstain abstain abstain abstain method abstain abstain abstain abstain other abstain abstain method abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain other abstain abstain other abstain abstain abstain method abstain abstain abstain abstain other abstain other abstain abstain abstain abstain abstain method abstain abstain method abstain abstain method abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective other other other objective method method other other other other other other other objective abstain other abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain other abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain result result abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain result abstain abstain abstain abstain abstain result abstain result result result result abstain abstain abstain result abstain result result result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain result result abstain abstain objective abstain other other