Named entity recognition (NER) is a fundamental task in natural language processing. Recent works treat named entity recognition as a reading comprehension task, constructing type-specific queries manually to extract entities. This paradigm suffers from three issues. First, type-specific queries can only extract one type of entities per inference, which is inefficient. Second, the extraction for different types of entities is isolated, ignoring the dependencies between them. Third, query construction relies on external knowledge and is difficult to apply to realistic scenarios with hundreds of entity types. To deal with them, we propose Parallel Instance Query Network (PIQN), which sets up global and learnable instance queries to extract entities from a sentence in a parallel manner. Each instance query predicts one entity, and by feeding all instance queries simultaneously, we can query all entities in parallel. Instead of being constructed from external knowledge, instance queries can learn their different query semantics during training. For training the model, we treat label assignment as a one-to-many Linear Assignment Problem (LAP) and dynamically assign gold entities to instance queries with minimal assignment cost. Experiments on both nested and flat NER datasets demonstrate that our proposed method outperforms previous state-of-the-art models 1 . Named Entity Recognition (NER) aims to identify text spans to specific entity types such as Person, Location, Organization. It has been widely used in many downstream applications such as entity linking (Ganea and Hofmann, 2017; Le and Titov, 2018) and relation extraction (Li and Ji, 2014; * This work was conducted when Yongliang Shen was interning at Alibaba DAMO Academy. Miwa and Bansal, 2016; Shen et al., 2021b). Traditional approaches for NER are based on sequence labeling, assigning a single tag to each word in a sentence. However, the words of nested entities have more than one tag, thus these methods lack the ability to identify nested entities. Recently, Ju et al. (2018); Strakov et al. (2019); Wang et al. (2020a) redesign sequence labeling models to support nested structures using different strategies. Instead of labeling each word, Luan et al. (2019); Tan et al. (2020); Li et al. (2021); Shen et al. (2021a) perform a classification task on the text span, and Strakov et al. (2019); Paolini et al. (2021); Yan et al. (2021); Tan et al. (2021) treat NER as a sequence generation or set prediction task and design encoder-decoder models to generate entities. Recently, Li et al. (2020b); Mengge et al. (2020); Zheng et al. (2021) reformulate the NER task as a machine reading task and achieve a promising performance on both flat and nested datasets. As shown in Figure 1(a), they treat the sentence as context and construct type-specific queries from external knowledge to extract entities. For example, for the sentence "U.S. President Barack Obama and his wife spent eight years 947 in the White House" , Li et al. (2020b) constructs the PER -specific query in natural language form -"Find person entity in the text, including a single individual or a group" to extract the PER entities, such as "U.S. President" , "Barack Obama" . However, since the queries are type-specific, only one type of entities can be extracted for each inference. This manner not only leads to inefficient prediction but also ignores the intrinsic connections between different types of entities, such as "U.S." and "U.S. President" . In addition, type-specific queries rely on external knowledge for manual construction, which makes it difficult to fit realistic scenarios with hundreds of entity types. In this paper, we propose the Parallel Instance Query Network (PIQN), where global and learnable instance queries replace type-specific ones to extract entities in parallel. As shown in Figure 1(b), each instance query predicts one entity, and multiple instance queries can be fed simultaneously to predict all entities. Different from previous methods, we do not need external knowledge to construct the query into natural language form. The instance query can learn different query semantics during training, such as position-related or type-related semantics. Since the semantics of instance queries are implicit, we cannot assign gold entities as their labels in advance. To tackle this, we treat label assignment as a one-to-many Linear Assignment Problem (LAP) (Burkard and ela, 1999), and design a dynamic label assignment mechanism to assign gold entities for instance queries. Our main contributions are as follow:  Different from type-specific queries that require multiple rounds of query, our model employs instance queries that can extract all entities in parallel. Furthermore, the style of parallel query can model the interactions between entities of different types. Instead of relying on external knowledge to construct queries in natural language form, instance queries learn their query semantics related to entity location and entity type during training. To train the model, we design a dynamic one-to-many label assignment mechanism, where the entities are dynamically assigned as labels for the instance queries during training. The one-to-many manner allows multiple queries to predict the same entity, which can further improve the model performance. Experiments show that our model achieves state-of-the-art performance consistently on several nested and flat NER datasets. Traditional approaches for NER can be divided into three categories, including tagging-based, hypergraph-based and span-based approaches. The typical sequence labeling approach (Huang et al., 2015) predicts labels for each token, and struggles to address nested NER. Some works (Alex et al., 2007; Wang et al., 2020a) adapt the sequence labeling model to nested entity structures by designing a special tagging scheme. Different from the decoding on the linear sequence, the hypergraph-based approaches (Lu and Roth, 2015; Muis and Lu, 2017; Katiyar and Cardie, 2018) construct hy-pergraphs based on the entity nesting structure and decode entities on the hypergraph. Span-based methods first extract spans by enumeration (Sohrab and Miwa, 2018; Luan et al., 2019) or boundary identification (Zheng et al., 2019; Tan et al., 2020), and then classify the spans. Based on these, Shen et al. (2021a) treats NER as a joint task of boundary regression and span classification and proposes a two-stage identifier of locating entities first and labeling them later. Three novel paradigms for NER have recently been proposed, reformulating named entity recognition as sequence generation, set prediction, and reading comprehension tasks, respectively. Yan et al. (2021) formulates NER as an entity span sequence generation problem and uses a BART (Lewis et al., 2020) model with the pointer mechanism to tackle NER tasks. Tan et al. (2021) formulates NER as an entity set prediction task. Different from Strakov et al. (2019), they utilize a non-autoregressive decoder to predict entity set. Li et al. (2020b); Mengge et al. (2020) reformulate the NER task as an MRC question answering task. They construct type-specific queries using semantic prior information for entity categories. Different from Li et al. (2020b); Jiang et al. (2021), our method attempts to query at the entity level, where it adaptively learns query semantics for instance queries and extracts all types of entities in parallel. It is worth noting that Seq2Set (Tan et al., 2021) is quite different from ours: (1) 948 Seq2Set attempts to eliminate the incorrect bias introduced by specified entity decoding order in the seq2seq framework, and proposes an entity set predictor, while we follow the MRC paradigm and focus on extracting entities using instance queries. (2) Seq2Set is an encoder-decoder architecture, while our model throws away the decoder and keeps only the encoder as in Wang et al. (2022a), which speeds up inference and allows full interaction between query and context. (3) Seq2Set uses bipartite graph matching to compute the entity-set level loss, while we focus on the label assignment for each instance query and propose a one-to-many dynamic label assignment mechanism. In this section, we first introduce the task formulation in  3.1, and then describe our method. As shown in Figure 2, our method consists of three components: the Encoder ( 3.2), the Entity Prediction ( 3.3) and the Dynamic Label Assignment ( 3.4). The encoder encodes both the sentence and instance queries. Then for each instance query, we perform entity localization and entity classification using Entity Pointer and Entity Classifier respectively. For training the model, we introduce a dynamic label assignment mechanism to assign gold entities to the instance queries in  3.4. We use ( X, Y ) to denote a training sample, where X is a sentence consisting of N words labeled by a set of triples Y = { < Y lk , Y rk , Y tk > } G  1 k =0 . Y lk  [0 , N  1] , Y rk  [0 , N  1] and Y tk  E are the indices for the left boundary, right boundary and entity type of the k -th entity, where E is a finite set of entity types. In our approach, We set up M ( M > G ) global and learnable instance queries I = RM  h , each of which (denoted as a vector of size h ) extracts one entity from the sentence. They are randomly initialized and can learn the query semantics automatically during training. Thus we define the task as follows: given an input sentence X , the aim is to extract the entities Y based on the learnable instance queries I . Model input consists of two sequences, the sentence X of length N and the instance queries I of length M . The encoder concatenates them into one sequence and encodes them simultaneously. Input Embedding We calculate the token embeddings E tok , position embeddings E pos and type embeddings E typ of the input from two sequences as follows ( E tok , E pos , E typ  R ( N + M )  h ): E tok = Concat( V, I ) E pos = Concat( P w , P q ) E typ = Concat([ U w ] N , [ U q ] M ) (1) where V  RN  h are token embeddings of the word sequence, I  RM  h are the vectors of instance queries, P w  RN  h and P q  RM  h are separate learnable position embeddings. U w and U q are type embeddings and [  ] N means repeating N times. Then the input can be represented as H 0 = E tok + E pos + E typ  R ( N + M )  h . One-Way Self-Attention Normal self-attention would let the sentence interact with all instance queries. In such a way, randomly initialized instance queries can affect the sentence encoding and break the semantics of the sentence. To keep the sentence semantics isolated from the instance queries, we replace the self-attention in BERT (De-vlin et al., 2019) with the one-way version: OW-SA( H ) = HW v (2)  = softmax (cid:18) HW q ( HW k ) T  h + M (cid:19) (3) where W q , W k , W v  R h  h are parameter matrices and M  { 0 ,  inf } ( N + M )  ( N + M ) is a mask matrix for the attention score where elements in M set to 0 for kept units and  inf for removed ones. In our formula, the upper right sub-matrix of M is a full  inf matrix of size ( N  M ) and other elements are zero, which can prevent the sentence encoding from attending on the instance queries. In addition, the self-attention among instance queries can model the connections between each other, and then enhance their query semantics. After BERT encoding, we further encode the sequence at word-level by two bidirectional LSTM layers and L extra transformer layers. Finally we split H  R ( N + M )  h into two parts: the sentence encoding H w  RN  h and the instance query encoding H q  RM  h . Each instance query can predict one entity from the sentence, and with M instance queries, we can predict at most M entities in parallel. Entity prediction 949 Hungarian Algorithm (0, 0, GPE)  (2, 3, PER) (11, 13, FAC) None  Optimal Assignment ( * )  0 1 2 M-2 M-1 Assign None label Entity Pointer Entity Classifier  0 1  2 Encoder Sentence M Instance Queries Barack Obama (2, 3, PER ) PER FAC GPE  L [2] & R [2] L [1] R [1] L [M-1] R [M-1] T [1] T [M-1] T [2] P tiYt k P liYl k P riY r k Cost i k = + + ( ( -M-2 M-3 M-4 V [CLS] P 0 U w I M-1 U q P M-1 I M-2 UP M-2 q I M-3 UP M-3q I M-4 U P M-4 q    I 2 UP 2 q I 1 U P 1q I 0 UP 0 q V [SEP] P N-1 U w V House P N-2 U w V White P N-3 U w V the P N-4 U w    V Obama P 4 U w V Barack P 3 U w V President P 2 U w V U.S. P 1 U w Token Position Type Assignment Matrix ( A ) Entity Prediction Dynamic Label Assignment Y G-2 Y G-1 Y 0 Cost Matrix ( Cost ) Y 1 Assignable Quantity ( q ) -1.7 -0.6 -1.0 -1.2 -2.7 -0.8 -0.9 -1.2 -2.8 -1.1 -1.0 -1.2 -1.9 -0.9 -0.7   -2.9 -0.8 -1.0 -0.7 -2.8 1 2  1 1   G ground-truth entities Y = ( Y k , Y k , Y k ) l r t M l a b e l e d i n s t a n ce qu e r i e s 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0   1 0 0 0 1 0 0 0 1 0 Y G-2 Y G-1 Y 0 Y 1 None   P t P l P r M un l a b e l e d i n s t a n ce qu e r i e s w w w w w w w w w q q q q q q q M-1 Figure 2: The overall architecture of the model. can be viewed as a joint task of boundary prediction and category prediction. We design Entity Pointer and Entity Classifier for them respectively. Entity Pointer For the i -th instance query H qi , we first interact the query with each word of the sentence by two linear layers. The fusion representation of the i -th instance query and j -th word is computed as: S  ij = ReLU( H q i W q  + H w j W w  ) (4) where   { l, r } denotes the left or right boundary and W q , W w  R h  h are trainable projection parameters. Then we calculate the probability that the j -th word of the sentence is a left or right boundary: P ij = sigmoid( S ij W  + b  ) (5) where W   R h and b  are learnable parameters. Entity Classifier Entity boundary information are useful for entity typing. We use P i = [ P i 0 , P i 1 ,    , P iN  1 ] ,   { l, r } to weigh all words and then concatenate them with instance queries. where W qt  R h  h is a learnable parameter. Then we can get the probability of the entity queried by the i -th instance query belonging to category c : P t ic = exp( S t i W c t + b c t ) (cid:80) c  E exp( S ti W c  t + b c  t ) (7) where W c  t  R h and b c  t are learnable parameters. Finally, the entity predicted by the i -th instance query is T i = (cid:0) T li , T ri , T ti (cid:1) . T li = arg max j ( P lij ) and T ri = arg max j ( P rij ) are the left and right boundary, T ti = arg max c ( P tic ) is the entity type. We perform entity localization and entity classification on all instance queries to extract entities in parallel. If multiple instance queries locate the same entity but predict different entity types, we keep only the prediction with the highest classification probability. Dynamic Label Assignment Since instance queries are implicit (not in natural language form), we cannot assign gold entities to them in advance. To tackle this, we dynamically assign labels for the instance queries during training. Specifically, we treat label assignment as a Linear Assignment Problem. Any entity can be assigned to any instance query, incurring some cost that may vary depending on the entity-query assignment. We define the cost of assigning the k -th entity ( Y k = < Y lk , Y rk , Y tk >) to the i -th instance query as: Cost ik =  (cid:16) P tiY tk + P liY lk + P riY rk (cid:17) (8) where Y tk , Y lk and Y rk denote the indices for the entity type, left boundary and right boundary of the k -th entity. It is required to allocate as many entities as possible by assigning at most one entity to each query and at most one query to each entity, in such a way that the total cost of the assignment is minimized. However, the one-to-one manner does not fully utilize instance queries, and many instance queries are not assigned to gold entities. Thus we extend the traditional LAP to one-to-many one, where each entity can be assigned to multiple instance queries. The optimization objective of this one-to-many LAP is defined as: min M  1 (cid:88) i =0 G  1 (cid:88) k =0 A ik Cost ik s.t. (cid:80) k A ik  1 (cid:80) i A ik = q k  i, k, A ik  { 0 , 1 } . where A  { 0 , 1 } M  G is the assignment matrix, G denotes the number of the entities and A ik = 1 indicates the k -th entity assigned to the i -th instance query. q k denotes the assignable quantity of the k -th gold entity and Q = (cid:80) k q k denotes the total assignable quantity for all entities. In our experiments, the assignable quantities of different entities are balanced. We then use the Hungarian (Kuhn, 1955) algorithm to solve Equation 9, which yields the label assignment matrix with the minimum total cost. However, the number of instance queries is greater than the total assignable quantity of entity labels ( M > Q ), so some of them will not be assigned to any entity label. We assign None label to them by extending a column for the assignment matrix. Based on the new assignment matrix  A  { 0 , 1 } M  ( G +1) , we can further get the labels  Y = Y. indexby(   ) for M instance queries, where   = arg max dim =1 (  A ) is the label index vector for instance queries under the optimal assignment. Training Objective We have computed the entity predictions for M instance queries in  3.3 and got their labels  Y with the minimum total assignment cost in  3.4. To train the model, we define boundary loss and classification loss. For left and right boundary prediction, we use binary cross entropy function as a loss: L b =  (cid:88)  { l,r } M  1 (cid:88) i =0 N  1 (cid:88) j =0 1 [  Y i = j ] log P ij + 1 [  Y i  = j ] log (cid:16) 1  P ij (cid:17) (11) and for entity classification we use cross entropy function as a loss: L t =  M  1 (cid:88) i =0 (cid:88) c E 1 [  Y ti = c ] log P tic (12) where 1 [  ] denotes indicator function that takes 1 when  is true and 0 otherwise. Follow Al-Rfou et al. (2019) and Carion et al. (2020), we add Entity Pointer and Entity Classifier after each word-level transformer layer, and we can get the two losses at each layer. Thus, the total loss on the train set D can be defined as: L = (cid:88) D L (cid:88)  =1 L t + L b (13) where L t , L b are classification loss and boundary loss at the  -th layer. For prediction, we just perform entity prediction at the final layer. To provide empirical evidence for the effectiveness of the proposed model, we conduct our experiments on eight English datasets, including five nested NER datasets: ACE04 (Doddington et al., 2004) , ACE05 (Walker et al., 2006), KBP17 (Ji et al., 2017), GENIA (Ohta et al., 2002), NNE(Ringland et al., 2019) and three flat NER dataset: FewNERD (Ding et al., 2021), CoNLL03 (Tjong Kim Sang and De Meulder, 2003), OntoNotes (Pradhan et al., 2013), and one Chinese flat NER dataset: MSRA (Levow, 2006). FewNERD and NNE are two datasets with large entity type inventories, containing 66 and 114 fine-grained entity types. Please refer to Appendix A for statistical information about the datasets. In our experiments, we use pretrained BERT (Devlin et al., 2019) in our encoder. For a fair comparison, we use bert-large on ACE04, ACE05, NNE, CoNLL03 and OntoNotes, bert-base on KBP17 and FewNERD, biobert-large (Chiu et al., 2016) on GENIA and chinese-bert-wwm (Cui et al., 2020) on Chinese MSRA. For all datasets, we train our model for 30-60 epochs and use the Adam Optimizer (Kingma and Ba, 2015) with a linear warmup-decay learning rate schedule. We initialize all instance queries using the normal distribution N (0 . 0 , 0 . 02) . See Appendix B for more detailed parameter settings and Appendix C for all baseline models. We use strict evaluation metrics that an entity is confirmed correct when the entity boundary and the entity type are correct simultaneously. We employ precision, recall and F1-score to evaluate the performance. We also report the F1-scores on the entity localization and entity classification subtasks in  5.2 and Appendix D.2. We consider the localization as correct when the left and right boundaries are predicted correctly. Based on the accurately localized entities, we then evaluate the performance of entity classification. Overall Performance Table 1 illustrates the performance of the proposed model as well as baselines on the nested NER datasets. We observe significant performance boosts on the nested NER datasets over previous state-of-the-art models, 952 achieving F1-scores of 81.77%, 88.14%, 87.42% and 84.50% on GENIA, ACE04, ACE05, KBP17 and NNE datasets with +1.23%, +0.73%, +0.37%, +0.45% and +0.96% improvements. Our model can be applied to flat NER. As shown in Table 2, our model achieves state-of-the-art performance on the FewNERD and Chinese MSRA datasets with +1.44% and +0.88% improvements. On the CoNLL03 and OntoNotes datasets, our model also achieves comparable results. Compared with the type-specific query-based method (Li et al., 2020b), our model improves by +2.85%, +2.16%, +0.54%, +3.53% on the GENIA, ACE04, ACE05 and KBP17 datasets. We believe there are three reasons: (1) Rather than relying on external knowledge to inject semantics, instance queries can learn query semantics adaptively, avoiding the sensitivity to hand-constructed queries of varying quality. (2) Each query no longer predicts a group of entities of a specific type, but only one entity. This manner refines the query to the entity level with more precise query semantics. (3) Instance queries are fed into the model in parallel for encoding and prediction, and different instance queries can exploit the intrinsic connections between entities. Inference Speed We compare the inference speed on ACE04 and NNE, as shown in Table 4. Compared to the type-specific query method (Li et al., 2020b), our model not only improves the performance, but also gains significant inference speedup. In particular, on the NNE dataset with 114 entity types, our model speeds up by 30.46  and improves performance by +39.2%. This is because Li et al. (2020b) requires one inference for each type-specific query, while our approach performs parallel inference for all instance queries and only needs to be run once. We also compare previous state-of-the-art models (Tan et al., 2021; Shen et al., 2021a) and our method is still faster and performs better. In this section, we analyze the effects of different components in PIQN. As shown in Table 3, we have the following observations: (1) Compared to the static label assignment in order of occurrence, the dynamic label assignment shows significant improvement on localization, classification, and NER F1-score, which improves NER F1-score by +5.71% on ACE04 and +8.84% on GENIA. This shows that modeling label assignment as a LAP Model FewNERD Pr. problem enables dynamic assignment of optimal labels to instance queries during training, eliminating the incorrect bias when pre-specifying labels. Furthermore, one-to-many for label assignment is more effective than one-to-one, improving the F1-score by +3.86% on ACE04 and +0.51% on GENIA. (2) The one-way self-attention blocks the attention of sentence encoding on instance queries, which improves the F1-score by +0.98% on ACE04 and +0.57% on GENIA. It illustrates the importance of keeping the semantics of the sentence independent of the query. In contrast, semantic interactions between queries are effective, which improves the F1-score by +0.92% on ACE04 and +0.67% on GENIA. The major reason is that entities in the same sentence are closely related and the interaction between instance queries can capture the relation between them. In order to analyze the query semantics learned by the instance query in the training, we randomly selected several instance queries and analyzed the locations and types of entities they predicted. Entity Location We normalize the predicted central locations of the entities and use kernel density estimation to draw the distribution of the predicted entity locations for different queries, as shown in Figure 3. We observe that different instance queries focus on entities at different positions, which means that the instance queries can learn the query semantics related to entity position. For example, instance queries #28 and #39 prefer to predict entities at the beginning of sentences, while #11 and #53 prefer entities at the end. Entity Type We count the co-occurrence of different instance queries and different entity types they predicted. To eliminate the imbalance of entity types, we normalize the co-occurrence matrix on the entity type axis. As shown in Figure 4, different instance queries have preferences for different entity types. For example, instance queries #11 and #13 prefer to predict PER entities, #30 and #43 prefer VEH entities, #25 and #49 prefer WEA entities, #12 prefers FAC entities, and #35 prefers LOC entities. We also analyze the auxiliary loss, the dynamic label assignment mechanism, and the performance on entity localization and classification, please see the Appendix D. Table 5 shows a case study about model predictions. Our model can recognize nested entities and 954 # Sentence with Gold Entities Prediction  Instance Query IDs 1 [ 0 A number of powerful international companies and commercial agencies , such as [ 12 Ito Bureau of [ 15 Japan 15 ] GPE15 ] ORG , [ 17 Han Hua Group of [ 21 South Korea 22 ] GPE22 ] ORG , [ 24 Jeffrey Group of [ 27 the US 28 ] GPE28 ] ORG , [ 30 etc 30 ] ORG30 ] ORG . long entities well. In case 1, the entities of length 31 or with the three-level nested structure are predicted accurately. And thanks to the one-to-many dynamic label assignment mechanism, each entity can be predicted by multiple instance queries, which guarantees a high coverage of entity prediction. However, the model's ability to understand sentences is still insufficient, mainly in the following ways: (1) There is a deficiency in the understanding of special phrases. Yahoo ! Communications Services in case 2 is misclassified as ORG , but in fact Yahoo ! is ORG . (2) Over-focus on local semantics. In case 3, the model misclassifies Venezuelan consumer as PER , ignoring the full semantics of the long phrase the Venezuelan consumer protection agency , which should be ORG . (3) Insensitivity to morphological variation. The model confused Venezuelan and Venezuela , and misidentified the former as GPE in case 3. In this paper, we propose Parallel Instance Query Network for nested NER, where a collection of instance queries are fed into the model simultaneously and can predict all entities in parallel. The instance queries can automatically learn query semantics related to entity types or entity locations during training, avoiding manual constructions that rely on external knowledge. To train the model, we design a dynamic label assignment mechanism to assign gold entities for these instance queries. Experiments on both nested and flat NER datasets demonstrate that the proposed model achieves state-of-the-art performance. This work is supported by the Key Research and Development Program of Zhejiang Province, China (No. 2021C01013), the National Key Research and Development Project of China (No. 2018AAA0101900), the Chinese Knowledge Center of Engineering Science and Technology (CK-CEST) and MOE Engineering Research Center of Digital Library.
abstain abstain abstain abstain abstain abstain objective method abstain method objective abstain method abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain objective abstain abstain method abstain abstain method objective objective objective method objective result other other other other other other other other other other other other method abstain abstain objective method method abstain method method method abstain method abstain abstain abstain abstain method abstain abstain abstain abstain method abstain abstain method method method other abstain method abstain abstain abstain abstain method abstain abstain abstain abstain method method abstain method abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method method abstain method abstain other abstain abstain method method method method abstain method method abstain method method abstain result abstain result result result abstain abstain abstain abstain result result result abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain result result abstain abstain abstain abstain abstain result abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective abstain method abstain other