An Effective Transition-based Model for Discontinuous NER (2020)

Abstract: Unlike widely used Named Entity Recognition (NER) data sets in generic domains, biomedical NER data sets often contain mentions consisting of discontinuous spans. Conventional sequence tagging techniques encode Markov assumptions that are efficient but preclude recovery of these mentions. We propose a simple, effective transition-based model with generic neural encoding for discontinuous NER. Through extensive experiments on three biomedical data sets, we show that our model can effectively recognize discontinuous mentions without sacrificing the accuracy on continuous mentions.

## introduction named entity recognition (ner) is a critical component of biomedical natural language processing applications. in pharmacovigilance, it can be used to identify adverse drug events in consumer reviews in online medication forums, alerting medication developers, regulators and clinicians @xcite @xcite . in clinical settings, ner can be used to extract and summarize key information from electronic medical records such as conditions hidden in unstructured doctors' notes @xcite . these applications require identification of complex mentions not seen in generic domains @xcite . widely used sequence tagging techniques (flat model) encode two assumptions that do not always hold: (1) mentions do not nest or overlap, therefore each token can belong to at most one mention; and, (2) mentions comprise continuous sequences of tokens. nested entity recognition addresses violations of the first assumption @xcite @xcite . however, the violation of the left atrium is mildly dilated . ## prior work existing methods on discontinuous ner can be mainly categorized into two categories: token level approach, based on sequence tagging techniques, and sentence level approach, where a combination of mentions within a sentence is jointly predicted @xcite . token level approach sequence tagging model takes a sequence of tokens as input and outputs a tag for each token, composed of a position indicator (e.g., bio schema) and an entity type. the vanilla bio schema cannot effectively represent discontinuous, overlapping mentions, therefore, some studies overcome this limitation via expanding the bio tag set @xcite @xcite . in addition to bio indicators, four new position indicators are introduced in (metke-jimenez and 1 code available at github: https://bit.ly/2xazeao @xcite to represent discontinuous mentions that may overlap: sentence level approach instead of predicting whether each token belongs to an entity mention and its role in the mention, sentence level approach predicts a combination of mentions within a sentence. a hypergraph, proposed by @xcite and extended in (muis and @xcite , can compactly represent discontinuous and overlapping mentions in one sentence. a sub-hypergraph of the complete hypergraph can, therefore, be used to represent a combination of mentions in the sentence. for the token at each position, there can be six different node types: using this representation, a single entity mention can be represented as a path from node a to node x, incorporating at least one node of type b. note that both token level and sentence level approaches predict first an intermediate representation of mentions (e.g., a sequence of tags in @xcite and a sub-hypergraph in (muis and lu, 2016)), which are then decoded into the final mentions. during the final decoding stage, both models suffer from some level of ambiguity. taking the sequence tagging model using bio variant schema as an example, even if the model can correctly predict the gold sequence of tags for the example sentence 'muscle pain and fatigue' (bh i o bd), it is still not clear whether the token 'muscle' forms a mention by itself, because the same sentence containing three mentions ('muscle', 'muscle pain' and 'muscle fatigue') can be encoded using the same gold sequence of tags. we refer to a survey by @xcite for more discussions on these models, and (muis and @xcite for a theoretical analysis of ambiguity of these models. similar to prior work, our proposed transitionbased model uses an intermediate representation (i.e., a sequence of actions). however, it does not suffer from this ambiguity issue. that is, the output sequence of actions can always be unambiguously decoded into mention outputs. the other two methods that focus on the discontinuous ner problem in literature are described in @xcite . @xcite solve the ner task as a structured multi-label classification problem. instead of starting and ending indices, they represent each entity mention using the set of token positions that belong to the mention. this representation is flexible, as it allows mentions consisting of discontinuous tokens and does not require mentions to exclude each other. however, this method suffers from high time complexity. @xcite compare this representation with bio variant schema proposed in @xcite , and found that they achieve competitive f 1 scores, although the latter method is more efficient. a twostage approach that first detects all components and then combines components into discontinuous mentions based on a classifier's decision was explored in recent work by @xcite . discontinuous ner vs. nested ner although discontinuous mentions may overlap, we discriminate this overlapping from the one in nested ner. that is, if one mention is completely contained by the other, we call mentions involved nested entity mentions. in contrast, overlapping in discontinuous ner is usually that two mentions overlap, but no one is completely contained by the other. most of existing nested ner models are built to tackle the complete containing structure @xcite , and they cannot be directly used to identify overlapping mentions studied in this paper, nor mention the discontinuous mentions. however, we note that there is a possible perspective to solve discontinuous ner task by adding fine-grained entity types into the schema. taking the second sentence in figure 1 have much muscle pain and fatigue . as an example, we can add two new entity types: 'body location' and 'general feeling', and then annotate 'muscle pain and fatigue' as a 'adverse drug event' mention, 'muscle' as a 'body location' mention, and 'pain' and 'fatigue' as 'general feeling' mentions (figure 2 ). then the discontinuous ner task can be converted into a nested ner task. ## model transition-based models, due to their high efficiency, are widely used for nlp tasks, such as parsing and entity recognition @xcite @xcite . the model we propose for discontinuous ner is based on the shift-reduce parser @xcite that employs a stack to store partially processed spans and a buffer to store unprocessed tokens. the learning problem is then framed as: given the state of the parser, predict an action which is applied to change the state of the parser. this process is repeated until the parser reaches the end state (i.e., the stack and buffer are both empty). the main difference between our model and the ones in @xcite is the set of transition actions. @xcite use shift, reduce, unary, finish, and idea for the constituent parsing system. @xcite use shift, reduce, out for the flat ner system. inspired by these models, we design a set of actions specifically for recognizing discontinuous and overlapping structure. there are in total six actions in our model: figure 3 shows an example about how the parser recognizes entity mentions from a sentence. note that, given one parser state, not all types of actions are valid. for example, if the stack does not contain any span, only shift and out actions are valid because all other actions involve popping spans from the stack. we employ hard constraints that we only select the most likely action from valid actions. ## data sets although some text annotation tools, such as brat @xcite , allow discontinuous annotations, corpora annotated with a large number of discontinuous mentions are still rare. we use three data sets from the biomedical domain: cadec @xcite , share 13 @xcite and share 14 @xcite . around 10% of mentions in these three data sets are discontinuous. the descriptive statistics are listed in cadec is sourced from askapatient 2 , a forum where patients can discuss their experiences with medications. the entity types in cadec include drug, adverse drug event (ade), disease and symptom. we only use ade annotations because only the ades involve discontinuous annotations. this also allows us to compare our results directly against previously reported results @xcite . share 13 and 14 focus on the identification of disorder mentions in clinical notes, including discharge summaries, electrocardiogram, echocardiogram, and radiology reports @xcite mapped to a concept in the disorder semantic group of snomed-ct @xcite . although these three data sets share similar field (the subject matter of the content being discussed), the tenor (the participants in the discourse, their relationships to each other, and their purposes) of cadec is very different from the share data sets @xcite . in general, laymen (i.e., in cadec) tend to use idioms to describe their feelings, whereas professional practitioners (i.e., in share) tend to use compact terms for efficient communications. this also results in different features of discontinuous mentions between these data sets, which we will discuss further in § 7. experimental setup as cadec does not have an official train-test split, we follow metke-jimenez and @xcite and randomly assign 70% of the posts as the training set, 15% as the development set, and the remaining posts as the test set. 3 the train-test splits of share 13 and 14 are both from their corresponding shared task settings, except that we randomly select 10% of documents from each training set as the development set. micro average strict match f 1 score is used to evaluate the effectiveness of the model. the trained model which is most effective on the development set, measured using the f 1 score, is used to evaluate the test set. ## baseline models we choose one flat ner model which is strong at recognizing continuous mentions, and two discontinuous ner models as our baseline models: recall that the flat model cannot be directly applied to data sets containing discontinuous mentions. following the practice in @xcite , we replace the discontinuous mention with the shortest span that fully covers it, and merge overlapping mentions into a single mention that covers both. note that, different from @xcite , we apply these changes only on the training set, but not on the development set and the test set. ## experimental results when evaluated on the whole test set, our model outperforms three baseline models, as well as over previous reported results in the literature, in terms of recall and f 1 scores ( the graph-based model achieves highest precision, but with substantially lower recall, therefore obtaining lowest f 1 scores. in contrast, our model improves recall over flat and bio extension models as well as previously reported results, without sacrificing precision. this results in more balanced precision and recall. improved recall is especially encouraging for our motivating pharmacovigilance and medical record summarization applications, where recall is at least as important as precision. ## analysis we start our analysis from characterizing discontinuous mentions from the three data sets. then we measure the behaviors of our model and two discontinuous ner models on the development sets based on characteristics identified and attempt to draw conclusions from these measurements. ## summary we propose a simple, effective transition-based model that can recognize discontinuous mentions without sacrificing the accuracy on continuous mentions. we evaluate our model on three biomedical data sets with a substantial number of discontinuous mentions. comparing against two existing discontinuous ner models, our model is more effective, especially in terms of recall.