Global Span Selection for Named Entity Recognition (2022)

Abstract: Named Entity Recognition (NER) is an important task in Natural Language Processing with applications in many domains. In this paper, we describe a novel approach to named entity recognition, in which we output a set of spans (i.e., segmentations) by maximizing a global score. During training, we optimize our model by maximizing the probability of the gold segmentation. During inference, we use dynamic programming to select the best segmentation under a linear time complexity. We prove that our approach outperforms CRF and semi-CRF models for Named Entity Recognition. We will make our code publicly available.

## introduction named entity recognition is a crucial task in natural language processing whose purpose is to identify and classify salient entities in texts such as persons, organizations, and locations. recognizing such entities is advantageous for applications such as relation extraction and machine translation. there are two main paradigms for ner: sequence labeling (sl) @xcite @xcite and span-based approaches (sb) @xcite @xcite . sl frames ner as token-level prediction, using, for instance, the bio @xcite or bilou @xcite schemes, while sb considers spans (contiguous segments of tokens) as basic units instead of tokens and performs span-level classification by assigning a label to each entity and a special null label to non-entity spans. sl is usually performed by representing the tokens using deep learning models, then using a conditional random field @xcite as the output layer. the best label sequence is computed using the viterbi algorithm and learning typically maximizes the likelihood of gold sequences. in contrast, sb enumerates all candidate spans from an input text and computes their representation before feeding them into a softmax layer for classification. one advantage of sbs is that they allow richer span representation compared to sl since spanlevel features are learned end to end. however, such unstructured sb models predict the label of each span independently. they are prone to produce overlapping entities which is forbidden in flat and nested ner. prior works used a greedy decoding algorithm @xcite @xcite to obtain a set of non-overlapping entities. the highest-scoring entities are iteratively selected as long as they do not overlap with previously selected ones. greedy decoding is efficient but tends to suffer from myopic bias. choosing spans without regard to future decisions may results in suboptimal entity sets. an alternative formulation of ner as joint segmentation and labeling with semi-markov crfs has been proposed in the literature @xcite @xcite . this approach has two advantages: (a) it uses a globally-normalized model to compute the probability of each labeled segmentation as opposed to scoring each span independently; and (2) it guarantees no-overlap in the output entities by using a variant of the viterbi algorithm for decoding. nevertheless, semi-crfs underperform in practice as we show in our experiments. we hypothesise that scoring segmentations composed of entities and non-entities is the main weakness. first, nonentity spans can be segmented in multiple ways all equally valid but only one of them is enforced by the semi-crf, both during learning and inference. furthermore, the majority of spans are non-entity, a considerable probability mass is wasted on uninteresting segmentations. in this paper, we propose a new formulation for span-based ner that combines ideas from two-steps (filtering and decoding) approaches and globally-normalized crf-based models. our approach starts by filtering all non-entity spans using a span classifier and constructing an overlapping graph of the remaining spans. a globallynormalized model is then used to compute the probability of each maximal independent set (mis) within the graph. each such set corresponds to a selection of non-overlapping entities. learning and inference can be performed efficiently using dynamic programming as we explain in §2.2. furthermore, we train the span classifier and the global entity selection model jointly using a multi-task objective. we show that our approach outperforms both sl and semi-crfs on all tasks and outperform two-step (filtering and greedy decoding) models on most. ## two-step span-based ner state-of-the-art span-based approaches employ a locally-normalized, unstructured span classifier to filter non entity spans, followed by greedy decoding to select a set of non-overlapping entities @xcite . we describe these two steps in this section. ## conclusion in this work, we proposed a new approach for spanbased ner. during learning, our model maximizes the probability of the best segmentation while during inference, the final spans are selected according to a global score using dynamic programming. our model mitigates the myopic bias of the greedy decoding of the standard span-based approach and it scores best on most datasets compared to other structured models such as crf or semi-crf. for future work, it would be interesting to model the interaction between the spans to compute the global score.