A Fast and Sound Tagging Method for Discontinuous Named-Entity Recognition (2024)

Abstract: We introduce a novel tagging scheme for discontinuous named entity recognition based on an explicit description of the inner structure of discontinuous mentions. We rely on a weighted finite state automaton for both marginal and maximum a posteriori inference. As such, our method is sound in the sense that (1) well-formedness of predicted tag sequences is ensured via the automaton structure and (2) there is an unambiguous mapping between well-formed sequences of tags and (discontinuous) mentions. We evaluate our approach on three English datasets in the biomedical domain, and report comparable results to state-of-the-art while having a way simpler and faster model.

## introduction named-entity recognition (ner) is a fundamental natural language processing (nlp) task that aims at identifying mentions of named entities in texts. these mentions may for example refer to persons, organizations, locations or even dates, among others @xcite . over the years, this task has been extensively studied by the community, with contributions including decoding algorithms, neural network architectures, loss functions and methods for learning in different data availability situations, inter alia. there exists several variants of the ner problem, among which the most studied are flat ner and nested ner. the most common method for the flat case is bio tagging @xcite , where each word in a sentence is tagged depending on whether it is the begining of a mention (b), inside a mention (i) or outside a mention (o). 1 this tagging scheme can be augmented to disambiguate types, e.g. bloc and bper. an important benefit of bio tagging is that prediction has a linear time-1 see @xcite for other variants. complexity in the input length foot_0 using the viterbi algorithm @xcite , contrary to concurrent approaches like semi-markov models that have a quadratic time-complexity @xcite @xcite . a less studied task is discontinuous ner, where mentions are allowed to span discontinuous sequences of words. this problem is especially important for biomedical nlp. for example, pharmacovigilance aims to detect adverse drug reactions after a product is distributed in the market via automatic analysis of medical reports or social media @xcite . mentions of adverse drug reactions naturally occur in noncontiguous sequences, for example the sentence "the pain i was experiencing around the hipjoints was incredible" contains the mention "pain hipjoints" with a five word gap in the middle. several methods for discontinuous ner have been proposed in the literature, including transition models @xcite and other structured prediction approaches @xcite @xcite . unfortunately, they are more costly than bio tagging and require specialized neural network architectures. there have also been attempts to propose tagging schemes for discontinuous ner @xcite @xcite , but they all exhibit structural ambiguity (see section 5). in this work, we propose a novel tagging scheme for discontinuous ner that exploits the inner structure of discontinuous mentions. contrary to previous attempts, our approach is sound in the sense that: (1) there is no encoding ambiguity between sets of mentions and sequences of tags (i.e. there is a one-to-one mapping between the two representations); and (2) our prediction algorithm is con-strained to predict only well-formed sequences of tags (i.e. we can always reconstruct a set of mentions from a predicted tag sequence). to ensure well-formedness of predictions, we propose an algorithm based on inference in a weighted finitestate automaton. using our approach, the time complexity of maximum a posteriori inference for prediction is linear in the length of the input. moreover, our algorithm can be very efficiently implemented on gpu for batched inference @xcite . our contributions can be summarized as follows: our implementation is publicly available. 3 importantly, our decoding algorithm and all our loss functions can be used as a drop-in replacements in any bio tagger. as such, any future research in the bio tagging field may also be evaluated on discontinuous ner at no extra cost. in this section, we explain how we map discontinuous mentions into a two-layer representation that allows us to derive a new tagging scheme. although this transformation is generic, for ease of exposition we illustrate it on the particular case of adverse drug reactions. ## decoding algorithm without loss of generality, we assume all sentences have n words. let t be the tagset, x be the set of sentences and y the set of well-formed tag sequences. we represent a sequence of tags @xmath0, where each entry is associated with a tag and a word, i.e. @xmath1, 1} n|t | . if the value of an entry is 1 (resp. 0), the associated tag is assigned to the associated word (resp. not assigned). note that y ⊂ {0, 1} n|t | is a strict subset of all such vectors, as each word must be assigned exactly one tag and that the resulting tag sequence must satisfy the constraints described in section 2.2. let f θ : @xmath2. we define the probability of a tag sequence @xmath3: computing a y (w) is called marginal inference due to its link with marginal probabilities @xcite . computing the most probable output is reduced to computing: in practice, we need to compute the term in equation ( 1 ) for training the model and the term in equation (2) for prediction. the difficulty stems from the restriction (in the sum and in the arg max search space) to the set of well-formed outputs y . we follow a long tradition in nlp @xcite @xcite @xcite @xcite and rely on a finite-state automaton to solve these inference problems. ## weakly-supervised learning the negative log-likelihood (nll) loss, ℓ(w; y) = -⟨y, w⟩ + a y (w) , requires knowledge of the gold output y. unfortunately, ner datasets only contains annotated mentions, but not their component types (e.g. we do not know which components are body parts and events). therefore, we need to resort on weakly-supervised learning to infer this information. ## related work tagging methods. @xcite proposed the biohd tagging scheme for discontinuous ner. a major issue of their approach is its structural ambiguity: several tag sequences can encode the same discontinuous mention, and different discontinuous mentions have the same associated tag sequence, see (muis and lu, 2016, section 3.1). a choice to resolve ambiguity has to be made when making a prediction, meaning that there are structures that cannot be predicted. moreover, this approach does not constrain the output tag sequence to be well-formed, i.e. it may not be possible to reconstruct mentions from a predicted tag sequence. the tagging scheme used by @xcite and @xcite has the same limitation. muis and lu (2016) proposed a graphbased method that ensures that predictions are wellformed, but their approach still exhibits structural ambiguity. other methods. @xcite rely on a two-step model that first predicts continuous spans (i.e. components) and then uses a separate classifier that combines them together. @xcite proposed a novel transition-based model. these two approaches are based on sequential predictions that are trained using gold intermediate outputs, which can lead to error propagation once a single mistake is made at test time. to resolve this problem, @xcite proposed a method that jointly predicts spans and their combination based on the maximal clique problem. a downside of these approaches is that they are more computationally costly (and therefore slower) than tagging methods. ## experiments we evaluate our approach on three standard english datasets for discontinuous named-entity recognition in the biomedical domain: cadec @xcite , share2013 (pradhan et al.) and share2014 @xcite . we pre-process the data using the script of @xcite . note that our tagging scheme cannot predict all discontinuous mentions in the data, i.e. there are sentences that we cannot convert to our representation. therefore, we remove these sentences from the training set. 11 data statistics are given in ## conclusion in this work, we propose a novel tagging scheme for discontinuous ner based on a two-layer representation of discontinuous mentions. our approach leads to result on par with state-of-the-art using a very simple neural network architecture. importantly, decoding with our model is very fast compared to previous work. our main objective with this work is to propose a simple plug-in method for discontinuous ner: any future work on models for bio tagging can now also be trivially evaluated on discontinuous ner. moreover, our approach is also fast to train, meaning that there is no significant cost overhead.