Negative sampling is highly effective in handling missing annotations for named entity recognition (NER). One of our contributions is an analysis on how it makes sense through introducing two insightful concepts: missampling and uncertainty. Empirical studies show low missampling rate and high uncertainty are both essential for achieving promising performances with negative sampling. Based on the sparsity of named entities, we also theoretically derive a lower bound for the probability of zero missampling rate, which is only relevant to sentence length. The other contribution is an adaptive and weighted sampling distribution that further improves negative sampling via our former analysis. Experiments on synthetic datasets and well-annotated datasets (e.g., CoNLL-2003) show that our proposed approach benefits negative sampling in terms of F1 score and loss convergence. Besides, models with improved negative sampling have achieved new state-of-the-art results on real-world datasets (e.g., EC). With powerful neural networks and abundant well-labeled corpora, named entity recognition (NER) models have achieved promising performances (Huang et al., 2015; Ma and Hovy, 2016; Akbik et al., 2018; Li et al., 2020a). However, in many scenarios, available training data is low-quality, which means a portion of named entities are absent in annotations. Fig. 1 depicts a sentence and its incomplete annotations. Fine-grained NER (Ling and Weld, 2012) is a typical case. Its training data is mainly obtained through applying weak supervision to unlabeled corpora. Past works (Shang et al., 2018b; Li et al., 2021a) find missing annotations impact NER models and refer this to unlabeled entity problem . ing that causes their poor performances. To eliminate this adverse impact, they propose a simple yet effective approach based on negative sampling. Compared with its counterparts (Li and Liu, 2005; Tsuboi et al., 2008; Shang et al., 2018b; Peng et al., 2019), this method is of high flexibility, without relying on external resources, heuristics, etc. While negative sampling has handled missing annotations well, there is no systematic study on how it works, especially what potential factors are involved. From a number of experiments, we find missampling and uncertainty both worth receiving attention. Missampling means that some unlabeled entities are mistakenly drawn into the set of training negatives by negative sampling. To quantitively describe this, we define missampling rate, the proportion of unlabeled entities in sampled negatives, for a sentence. Uncertainty indicates how hard a sampled negative is for NER models to recognize, and we use entropy to estimate it. Empirical studies show low missampling rate and high uncertainty are both indispensable for effectively applying negative sampling. Besides, based on the observation that entities are commonly sparse, we provide a lower bound for the probability of zero missampling rate with theoretical proof, which is only related to sentence length. Originally, Li et al. (2021a) adopt uniform sampling distribution for negative sampling. Inspired by former findings, we introduce a weighted sampling distribution to displace the uniform one, 7188 Positive Instances (  ) (1, 1, O) (1, 3, O)  (6, 7, O) (7, 7, O) (3, 5, O) (7, 7, O) sample (1, 2, PER) Sampled Negatives ( " ) All the Negatives (  ) (3, 5, O) (7, 7, O) (1, 2, PER) Training Instances [Mark Twain] PER said this in New York extract extract collect collect (6, 7, LOC) inaccessible Unlabeled Entities ( $ ) LOC Figure 2: An example to depict how negative sampling collects training negatives given an annotated sentence. The phrase marked by a red circle is an unlabeled entity. which takes missampling and uncertainty into account. Our distribution is purely computed from the predictions of an NER model. This means it coevolves with the model throughout the training process. The adaptive property of our method is appealing since it doesn't rely on manual annotations or additional models to indicate valuable negatives. We have conducted extensive experiments to verify the effectiveness of our weighed sampling distribution. Results on synthetic datasets and well-annotated datasets (e.g., OntoNotes 5.0) show that weighted sampling distribution improves negative sampling in performances and loss convergence. Notably, with improved negative sampling, our NER models have established new state-of-the-art performances on real-world datasets, like EC (Yang et al., 2018). 2 Preliminaries 2.1 Unlabeled Entity Problem Given an n -length sentence, x = [ x 1 , x 2 ,    , x n ] , an annotator (e.g., human) will mark a set of named entities from it as y = { y 1 , y 2 ,    , y m } . n is sequence length and m is set size. Every entity, y k , of the set, y , is denoted as a tuple, ( i k , j k , l k ) . ( i k , j k ) is the span of the entity that corresponds to the phrase, x i k ,j k = [ x i k , x i k +1 ,    , x j k ] , and l k is its label. Unlabeled entity problem occurs when some ground truth named entities, (cid:98) y , are missed by annotators, which means they are not contained in the labeled entity collection, y . In distantly supervised NER (Mintz et al., 2009; Ren et al., 2015; Fries et al., 2017), this is resulted from the limited coverage of external resources, such as predefined ontology. In other situations (e.g., fine-grained NER where manual annotation is extremely hard), the cause may be the negligence of human annotators. Take Fig. 2 as an example. The set of labeled entities is y = [(1 , 2 , PER)] , that of unlabeled entities is (cid:98) y = { (6 , 7 , LOC) } , and that of ground-truth entities is y  (cid:98) y . Let S denote the set that includes all spans of a sentence, x , except the ones of annotated named entities, y . Every span in this set is labeled with O", indicating that it's a possible negative. A standard training strategy for NER models is to minimize the loss on annotated positives, y , and all negative candidates, S . Unfortunately, since S might contain unlabeled entities in (cid:98) y , NER models are seriously misguided in training. To address this problem, (Li et al., 2021a) propose to circumvent unlabeled entities with negative sampling. The core idea is to uniformly sample a few negative candidates, (cid:101) y , from S for reliably training NER models. Under this scheme, the training instances contain sampled negatives, (cid:101) y , and positives from annotated entities, y . With them, y  (cid:101) y , a cross-entropy loss is incurred as J = (cid:88) ( i,j,l )  y  (cid:101) y  log P ( l | x i,j ;  ) . P ( l | x i,j ;  ) is the probability that the ground truth label of the span, ( i, j ) , is l and  represents the parameters of a model. Following Li et al. (2021a), our NER models are all span-based, which treat a span, instead of a single token, as the basic unit for labeling. Negative sampling is probable to avoid models being exposed to unlabeled entities. As Fig. 2 shows, the false negative, (6 , 7 , O) , is not involved 7189 Figure 3: The comparisons between changes of entity number and square root curve. in training. Li et al. (2021a) have empirically confirmed the effectiveness of negative sampling in handling unlabeled entities. However, there is no systematic study to explain how it works, and what factors are relevant. We analyze how negative sampling leads NER models that suffer from missing entity annotations to promising results from two angles: missampling and uncertainty. Missampling rate,  , is defined as, for a sentence, the proportion of unlabeled entities contained in sampled negatives, (cid:101) y . Formally, it's computed as  = 1  # { ( i, j, l ) | ( i, j, l )  (cid:98) y ; ( i, j, O) /  (cid:101) y } # (cid:101) y , where # is an operation that measures the size of an unordered set. The missampling rate  reflects the quality of training instances, y  (cid:101) y . A lower averaged rate over the whole dataset means that the NER model meets fewer unlabeled entities in training. Intuitively, this leads to higher F1 scores since there is less misguidance from missing annotations to the model. Hence, missampling is an essential factor for analysis. We design a simulation experiment to empirically verify the above intuition. Like Li et al. (2021a), we build synthetic datasets as follows. We start from a well-labeled dataset, i.e., CoNLL-2003 (Sang and De Meulder, 2003), and then mimic unlabeled entity problem by randomly masking manually annotated entities with a fixed probability p (e.g., 0 . 7 ). In this way, we can obtain unlabeled entities, (cid:98) y , and annotated entities, y , for every sentence, x . We can obtain different pairs of a missampling rate and an F1 score through running a negative sampling based model on different synthetic datasets. Table 1 demonstrates several cases, and we can see the trend that lower missamping rates lead to better performances. Therefore, we conclude that missampling affects the effectiveness of negative sampling. We also theoretically prove that negative sampling is very robust to unlabeled entities based on a natural property of named entities. Entity Sparsity. Unlike other sequence labeling tasks, such as syntactic chunking (Sang and Buch-holz, 2000) and part-of-speech tagging (Schmid, 1994), named entities (i.e., non-O" segments) are commonly sparse in NER datasets. Fig. 3 depicts some statistics of two common NER datasets, CoNLL-2003 and OntoNotes 5.0. The blue points are the averaged number of entities for sentences of fixed lengths. Every point stands on the center of a dashed line, whose length is the 1.6 variance of the entity numbers. The red curves are the square roots of sentence lengths. To avoid being influenced by rare events" we erase the points supported by too few cases (i.e., 20). From the above figure, we can see that the number of ground truth named entities (i.e., unlabeled entities, (cid:98) y , and annotated ones, y ) in a sentence is generally smaller than the square root of sentence length,  n . Empirically, we have # y +# (cid:98) y   n . Theorem 1. For a n -length sentence x , assume (cid:101) y is the set of sampled negatives with size  n  (0 <  < 1) via negative sampling. If the premise of entity sparsity holds, then the probability of zero missampling rate, i.e.,  = 0 , is bounded. where m = # y . The i -th product term is the probability that, at the i -th sampling turn, the i th sampled candidate doesn't belong to unlabeled entity set, (cid:98) y . Then we can derive the following inequalities: q  (cid:89) 0  i<  n  (cid:0) 1   n  m n ( n +1)2  m  i (cid:1)  (cid:89) 0  i<  n  (cid:0) 1   n n ( n +1)2  i (cid:1) > (cid:0) 1  2  n n ( n  1) + 2 (cid:1)  n  . The first inequality holds because of the assump-tion; the second one holds because  n  m n ( n +1)2  m  i is monotonically decreases as m increases, and m  0 ; the last inequality hold since  n n ( n +1)2  i increases with decreasing i , i <  n  , and  n   n . Because (1 + a ) b  1 + ba for a   1  b  1 and  n  < n + 1 , we have q > (cid:16) 1  2  n n ( n  1) + 2 (cid:17)  n   1  2( n + 1)  n n ( n  1) + 2 > 1  4   n n  1 . The right-most term monotonically increases with the sentence length n , and thus the probability of zero missampling rate for every sentence has a lower bound. This theorem shows that missampling rates for standard negative sampling are controllable, and implies why negative sampling succeeds in handling missing annotations. Assume P o ( l | x i,j ) is an oracle model that accurately estimates a label distribution over every span ( i, j ) . The uncertainty is defined as the entropy of this distribution: H ( L | X = x i,j ) = (cid:88) l  L  P o ( l | x i,j ) log P o ( l | x i,j ) , where L and X represent the label space and a span, x i,j , respectively. Note that the oracle model P o ( l | x i,j ) is generally unreachable. the common practice is to additionally train a model P ( l | x i,j ;  ) (see Sec. 2.2) to approximate it. Besides, the approximate model is learned on held-out training data to avoid overconfident estimation. Uncertainties essentially measure how difficult a case is for models to make a decision (Jurado et al., 2015). In active learning, uncertainty is used to mine hard unlabeled instances for human annotator (Settles, 2009). In our scenario, we suspect that the uncertainty of sampled negatives plays an important role in our training with negative sampling. We design an empirical experiment to verify our hypothesis. Specifically, we first randomly and equally split the entire training data with masked entities into two parts, and the first part is used to train an oracle model P o . For every sentence x in the second part, we then sample three subsets from S as training negatives: the first subset denoted by (cid:101) y t corresponding to the topk uncertainties, and the second denoted by (cid:101) y m corresponding to middlek uncertainties, and the third denoted by (cid:101) y b corresponding to the bottomk uncertainties, with k =  n  . Since missampling affects F1 scores as aforementioned, we eliminate the effect on missampling rate by setting  = 0 when constructing both subsets, i.e., neither subset contains 7191 any spans included in (cid:98) y . Finally, we respectively train three models on top of three negative subsets according to Eq. 1, and report their performances on test data in Table 2. We can see that the model trained on (cid:101) y t achieves the best performance, which validates our hypothesis. The previous section shows that the effectiveness of negative sampling is dependent on two factors: missampling and uncertainty. As a result, if we had considered both quantities when sampling negatives, we should see larger improvements from final models. In this section, we propose an adaptive and weighted sampling distribution based on these two factors. Unfortunately, since missampling rate is defined on top of the unlabeled entities (cid:98) y which is unknown in practice, it is not straightforward to apply missampling for improving negative sampling. Therefore, we assume that an oracle model, z i,j,l = P o ( l | x i,j ) , exists, which is likely to predict the ground-truth label for every span x i,j . Then we define a score v i,j as the difference between the score z i,j, O and the maximum label score on the span ( i, j ) : v i,j = z i,j, O  max l L z i,j,l . Intuitively, if v i,j is high, then z i,j, O is high and max l L z i,j,l is low. In other words, x i,j is likely to be with O" label and thus the missampling rate should be small. Hence sampling such a span as a negative won't hurt NER models. Note that max l L z i,j,l in the right hand acts as normalization, making v i,j comparable among different spans ( i, j ) . We also define an uncertainty score, u i,j , as the entropy of the label distribution for a span: u i,j = H ( L | X = x i,j ) =  (cid:88) l L z i,j,l log z i,j,l . As discussed in Sec. 3.2.2, training a NER model with the negatives of higher uncertainty scores, u i,j , brings better performances. Based on v i,j and u i,j , we design the following weighted sampling distribution to displace the uniform one when sampling k negatives from S without replacement:   r i,j = u i,j  (1 + v i,j )  e i,j = exp( r i,j /T ) (cid:80) ( i  ,j  , O) S exp( r i  ,j  /T ) , (4) where T  1 is a temperature to control the smoothness of sampling distribution. 1 is to make a trade-off between v i,j and u i,j : a high  will ensure a low missampling rate while a low  will ensure a high uncertainty score. To make our approach practical for use, we should specify how to approximate the oracle model, P o ( l | x i,j ) . In the simulation experiment in Sec. 3.2.1, the oracle model is a fixed model via standard negative sampling which is learned on held-out training data. It's natural to use such a fixed model to approximate the oracle model here. However, this will cause a side-effect that our approach is not self-contained due to its dependence on an external model. Consequently, we consider an adaptive style: directly using the NER model, P ( l | x i,j ;  ) , itself as the oracle model whose parameter  is learned during the training process. Under this scheme, T is scheduled as  C  c , where C is the number of training epochs and 0  c < C is the current epoch number. Since the NER model P ( l | x i,j ;  ) is not accurate in early epochs of training, a more uniform sampling distribution (i.e., higher T ) is safer for sampling negatives. Finally, we get a weighted sampling distribution with the NER model, P ( l | x i,j ;  ) , adaptively approximating the oracle model. Our training procedure is the same as that of vanilla negative sampling (see Fig. 2), except for sampling distribution. To evaluate our proposed variant (i.e., negative sampling w/ weighted sampling distribution) , we have conducted extensive experiments on under-annotated cases: synthetic datasets and real-world datasets. We also validate its superiority in well-annotated scenarios. The well-annotated datasets are CoNLL-2003 and OntoNotes 5.0. CoNLL-2003 contains 22137 sentences and is split into 14987 , 3466 , and 3684 sentences for training set, development set, and test set, respectively. OntoNotes 5.0 contains 76714 7192 Figure 4: The changes of F1 scores with training epochs on some synthetic datasets. sentences from a wide variety of sources. We follow the same format and partition as in Luo et al. (2020). The construction of synthetic datasets is based on well-annotated datasets and has been already described in Sec. 3. Following prior works (Nooralahzadeh et al., 2019; Li et al., 2021a), we adopt EC and NEWS as the real-world datasets. Both of them are collected by Yang et al. (2018). The data contains 2400 sentences annotated by human and is divided into three portions: 1200 for training set, 400 for development set, and 800 for test set. Yang et al. (2018) build an entity dictionary of size 927 and apply distant supervision on a raw corpus to get extra 2500 training cases. NEWS is constructed from MSRA (Levow, 2006). Training set is of size 3000 , development set is of size 3328 , and test set is of size 3186 are all sampled from MSRA. Yang et al. (2018) collect an entity dictionary of size 71664 and perform distant supervision on the remaining data to obtain extra 3722 cases for training. Both EC and NEWS contain massive incomplete annotations. NER models trained on them suffer from unlabeled entity problem . We adopt the same configurations for all the datasets. The dimensions of scoring layers are 256 . L2 regularization and dropout ratio are 10  5 and 0 . 4 , respectively. We set  = 8 . This setting is obtained via grid search. We use Adam (Kingma and Ba, 2014) to optimize models. Our models run on GeForceRTX 2080T. At test time, we convert the predictions from our models into IOB format and use conlleval 1 script to compute the F1 score. In all the experiments, the improvements of our models over the baselines are statistically significant with a rejection probability lower than 0 . 01 . We show how NER models with our proposed approach perform on two types of datasets: synthetic datasets (e.g., CoNLL-2003) and real-world datasets (e.g., EC). Synthetic datasets offer us a chance to qualitatively analyze how our approach reacts to changing mask probabilities. For example, we will show that weighted sampling distribution is beneficial in fast loss convergence. Real-world datasets provide more appropriate cases to evaluate NER models, since missing annotations are caused by limited knowledge resources, rather than intentional masking. Fig. 4 shows the changes of F1 scores from vanilla negative sampling and our proposed variant with training epochs. The synthetic datasets are constructed from OntoNotes 5.0. We can see that, compared with vanilla negative sampling, our proposed variant obtains far better performances on 1 https://www.clips.uantwerpen.be/conll2000/chunking/ conlleval.txt. the first few epochs and converges much faster. These results clearly verify the superiority of our weighted sampling distribution. Table 3 compares vanilla negative sampling with our proposed variant in terms of F1 score. We can draw two conclusions. Firstly, our approach greatly improves the effectiveness of negative sampling. For example, when masking probability p is 0 . 8 , we increase the F1 scores by 4 . 07% on CoNLL-2003 and 1 . 29% on OntoNotes 5.0. Secondly, our variant is still robust when unlabeled entity problem is very serious. Setting masking probability p from 0 . 5 to 0 . 9 , our performance on OntoNotes 5.0 only drops by 8 . 79% . By contrast, it's 32 . 33% for vanilla negative sampling. Real-world datasets contain a high percentage of partial annotations caused by distant supervision. Hence, the models trained on them are faced with serious unlabeled entity problem . Table 4 diagrams the results. The F1 scores of negative sampling and Partial CRF are from their papers. We have additionally reported the results of PU Learning 2 , Weighted Partial CRF 3 , 2 https://github.com/v-mipeng/LexiconNER. BERT-MRC 4 , and BERT-Biaffine Model 5 , using their codes. We can draw three conclusions from the table. Firstly, we can see that BERT-MRC and BERT-Biaffine Model both perform poorly on real-world datasets. This manifests the huge adverse impacts of unlabeled entities on models. Secondly, our variant has achieved new state-of-the-art results on the two datasets. Our scores outnumber those of vanilla negative sampling by 1 . 30% and 0 . 89% on them. Thirdly, to make fair comparisons, we also report the results of using Bi-LSTM, instead of BERT, as the sentence encoder. This version still notably surpasses prior methods on the two datasets. For example, compared with Weighted Partial CRF, our improvements are 6 . 57% on EC and 6 . 55% on NEWS. As a by-product, we also evaluate the effectiveness of the proposed method on the well-annotated datasets CoNLL-2003 and OntoNotes 5.0. As shown in Table 5, we have achieved excellent performances on well-annotated datasets. The F1 scores of baselines are copied from Li et al. (2021a). With our weighted sampling distribution, the results of negative sampling are improved by 0 . 28% 4 https://github.com/ShannonAI/mrc-for-flat-nested-ner. on CoNLL-2003 and 0 . 64% on OntoNotes 5.0. Our model even outperforms BERT-Biaffine Model by 0 . 19% on CoNLL-2003. Compared with a strong baseline, Flair Embedding, our improvements of F1 scores are 0 . 63% and 2 . 09% on the two datasets. These results further verify the effectiveness of the proposed sampling distribution. The comparison here is in fact unfair for our model, because negative sampling only utilizes a small part of negatives,  n  rather than n ( n +1)2  m (see Sec. 2 for the details of these numbers). We also have tried using all the negatives for training our model, and found the resulting performances significantly outnumber those of baselines. The purpose of Table 5 is to confirm that negative sampling even works well for situations with complete entity annotations. A number of NER models (Lample et al., 2016; Akbik et al., 2018; Clark et al., 2018; Li et al., 2020b, 2021b) based on end-to-end neural networks and well-labeled data have achieved promising performances. A representative work is Bi-LSTM CRF (Huang et al., 2015). However, in many situations (e.g., distantly supervised NER), these seemingly perfect models severely suffer from unlabeled entity problem , where massive named entities are not annotated in training data. There are some techniques developed by earlier works to mitigate this issue. Fuzzy CRF and AutoNER (Shang et al., 2018b) allow NER models to learn from high-quality phrases that might be potential named entities. Mining these phrases demands external resources (Shang et al., 2018a), which is not flexible for practical usage. Moreover, there is no guarantee that unlabeled entities are fully covered by these phrases. PU Learning (Peng et al., 2019; Mayhew et al., 2019) adopts a weighted training loss and assigns low weights to false negative instances. This approach is limited by requiring prior information or heuristics. Partial CRF (Yang et al., 2018; Jie et al., 2019) is an extension of CRF, which marginalizes the loss over all candidates that are compatible with the incomplete annotation. While being theoretically attractive, this approach still needs a portion of well-annotated data to obtain true negatives, which limits its use in real-world applications. For example, in fine-grained NER (Ling and Weld, 2012), all the training data are produced through weak supervision, and its manual annotation is very difficult, so obtaining enough high-quality data is not practical. Recently, Li et al. (2021a) find that unlabeled entities severely misguide the NER models during training. Based on this observation, they introduce a simple yet effective approach using negative sampling. It's much more flexible than other methods, without resorting to external resources, heuristics, etc. However, Li et al. (2021a) haven't well explained why negative sampling works and there are weaknesses in their principle analysis. In this paper, we first show two factors that affect how negative sampling avoids NER models from being impacted by missing annotations. Notably, a theoretical guarantee is provided for the zero missampling rate. Then, we propose weighted sampling distribution to further improve negative sampling based on our former findings. Negative sampling succeeds in handling missing annotations. In particular, the fine-grained NER module of our online text understanding service, TexSmart (Liu et al., 2021; Zhang et al., 2020), adopts this technique because of its massive low-quality training data. In this work, we have made two contributions. On the one hand, we analyze why negative sampling succeeds in handling unlabeled entity problem from two perspectives: missampling and uncertainty. Empirical studies show both low missampling rates and high uncertainties are essential for applying negative sampling. Based on entity sparsity, we also provide a theoretical lower bound for the probability of zero missampling rate. On the other hand, we propose an adaptive and weighted sampling distribution that takes missampling and uncertainty into account. We have conducted extensive experiments to verify whether this further improves the effectiveness of negative sampling. Results on synthetic datasets and well-annotated datasets show that our approach benefits in performances and loss convergence. With improved negative sampling, our NER models also have achieved new state-of-the-art results on real-world datasets (e.g., NEWS).
abstain objective abstain abstain objective abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain method method abstain method abstain other abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain method abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain method method abstain abstain abstain abstain abstain abstain method method abstain abstain abstain abstain method abstain method abstain method abstain abstain abstain method 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 result abstain abstain abstain result abstain abstain abstain other abstain result abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain result abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain result abstain result other abstain abstain result abstain abstain abstain abstain abstain result result abstain other other other other other other other other other other other other other other other other objective other objective abstain method objective method abstain method objective result result objective