Discontinuous Named Entity Recognition as Maximal Clique Discovery (2021)

Abstract: Named entity recognition (NER) remains challenging when entity mentions can be discontinuous. Existing methods break the recognition process into several sequential steps. In training, they predict conditioned on the golden intermediate results, while at inference relying on the model output of the previous steps, which introduces exposure bias. To solve this problem, we first construct a segment graph for each sentence, in which each node denotes a segment (a continuous entity on its own, or a part of discontinuous entities), and an edge links two nodes that belong to the same entity. The nodes and edges can be generated respectively in one stage with a grid tagging scheme and learned jointly using a novel architecture named Mac. Then discontinuous NER can be reformulated as a non-parametric process of discovering maximal cliques in the graph and concatenating the spans in each clique. Experiments on three benchmarks show that our method outperforms the state-of-the-art (SOTA) results, with up to 3.5 percentage points improvement on F1, and achieves 5x speedup over the SOTA model.

## introduction named entity recognition (ner) is the task of detecting mentions of real-world entities from text and classifying them into predefined types. ner benefits many natural language processing applications (e.g., information retrieval @xcite , relation extraction @xcite , and question answering @xcite ). ner methods have been extensively investigated and researchers have proposed effective ones. most prior approaches @xcite productive cough with white or bloody sputum nichols, 2016; @xcite @xcite cast this task as a sequence labeling problem where each token is assigned a label that represents its entity type. their underlying assumption is that an entity mention should be a short span of text @xcite , and should not overlap with each other. while such assumption is valid for most cases, it does not always hold, especially in clinical corpus @xcite . for example, figure 1 shows two discontiguous entity mentions with overlapping segments. thus, there is a need to move beyond continuous entities and devise methods to extract discontinuous ones. towards this goal, current state-of-the-art (sota) models can be categorized into two classes: combination-based and transition-based. combination-based models first detect all the overlapping spans and then learn to combine these segments with a separate classifier @xcite ; transition-based models incrementally label the discontinuous spans through a sequence of shift-reduce actions @xcite . although these methods have achieved reasonable performance, they continue to have difficulty with the same problem: exposure bias @xcite . specifically, combination-based methods use the gold segments to guide the classifier during the training process while at inference the input segments are given by a trained model, leading to a gap between training and inference @xcite . for transition-based models, at training time, the current action relies on the golden previ-ous actions, while in the testing phase, the entire action sequence is generated by the model. as a result, a skewed prediction will further deviate the predictions of the follow-up actions. such accumulated discrepancy may hurt the performance. in order to overcome the limitation of such prior works, we propose mac, a maximal clique discovery based discontinuous ner model. the core insight behind mac is that all (potentially discontinuous) entity mentions in the sentence can naturally form a segment graph by interpreting their contained continuous segments as nodes, and connecting segments of the same entity to each other as edges. then the discontinuous ner task is equivalent to finding the maximal cliques from the graph, which is a well-studied problem in graph theory. so, the question that remains is how to construct such a segment graph. we decompose it into two uncoupled subtasks, segment extraction (se) and edge prediction (ep) in mac. typically, given an ntoken sentence, two n × n tag tables are formed for se and ep respectively where each entry captures the interaction between two individual tokens. se is then regarded as a labeling problem where tags are assigned to distinguish the boundary tokens of each segment, which have benefits in identifying overlapping segments. ep is converted as the problem of aligning the boundary tokens of segments contained in the same entity. overall, the tag tables of se and ep are generated independently, and will be consumed together by a maximum clique searching algorithm to recover desired entities from them, thus immune from the exposure bias problem. we conducted experiments on three standard discontinuous ner benchmarks. experiments show that mac can effectively recognize discontinuous entity mentions without sacrificing the accuracy on continuous mentions. this leads to a new state-ofthe-art (sota) on this task, with substantial gains of up to 3.5% absolute percentage points over previous best reported result. lastly, we show that in the runtime experiments on gpu environments, mac is about five times faster than the sota model. joint extraction aims to detect entity pairs along with their relations using a single model @xcite . discontinuous ner is related to joint extraction where the discontiguous entities can be viewed as relation links between segments @xcite . our model is motivated by tplinker @xcite , which formulates joint extraction as a token pair linking problem by aligning the boundary tokens of entity pairs. the main differences between our model and tplinker are two-fold: (1) we propose a tailor-designed tagging scheme for recognizing discontinuous segments; (2) the maximal clique discovery algorithm is introduced into our model to accurately merge the discontinuous segments. maximal clique discovery is to find a clique of maximum size in a given graph @xcite . here, a clique is a subset of the vertices all of which are pairwise adjacent. maximal clique discovery finds extensive application across diverse domains @xcite @xcite . in this paper, we reformulate discontinuous ner as the task of maximal clique discovery by constructing a segment graph and leveraging the classic b-k backtracking algorithm @xcite to find all the maximum cliques as the entities. sever joint , shoulder and upper body pain sever joint , shoulder and upper body pain sever joint , shoulder and upper body pain sever joint , shoulder and upper body pain sever joint , shoulder and upper body pain sever joint , shoulder and upper body pain sever joint pain joint shoulder upper body sever shoulder pain sever upper body pain ade-b: sever ade-b: sever joint ade-i: shoulder ade-i: pain ade-i: upper body pain pob-s: joint pob-s: shoulder pob-s: upper body p o b a d e segment graph graph construction maximal clique discovery ## methodology in graph theory, a clique is a vertex subset of an undirected graph where every two vertices in the clique are adjacent, while a maximal clique is the one that cannot be extended by including one more adjacent vertex. that means each vertex in the maximal clique has close relations with each other, and no other vertex can be added, which is similar to the relations between segments in a discontinuous entity. based on this insight, we claim that discontinuous ner can be equivalently interpreted as discovering maximal cliques from a segment graph, where nodes represent segments that either form entities on their own or present as parts of a discontinuous entity, and edges connect segments that belong to the same entity mention. considering the maximum clique searching process is usually non-parametric @xcite , discontinuous ner is actually decomposed into two subtasks: segment extraction and edge prediction, to respectively create the nodes and edges of the segment graph. their prediction results can be generated independently with our proposed grid tagging scheme, and will be consumed together to construct a segment graph, so that the maximal clique discovery algorithm can be applied to recover desired entities. the overall extraction process is depicted in figure 2 . next, we will first introduce our grid tagging scheme and its decoding workflow. then we will detail the mac, a maximal clique discovery based discontinuous ner model based on this tagging scheme. ## conclusion in this paper, we reformulate discontinuous ner as the task of discovering maximal cliques in a segment graph, and propose a novel mac architecture. it decomposes the construction of segment graph as two independent 2-d grid tagging problems, and solves them jointly in one stage, addressing the exposure bias issue in previous studies. extensive experiments on three benchmark datasets show that mac beats the previous sota method by as much as 3.5 pts in f1, while being 5 times faster. further analysis demonstrates the ability of our model in recognizing discontinuous and overlapping entity mentions. in the future, we would like to explore similar formulation in other information extraction tasks, such as event extraction and nested ner.