Named Entity Recognition as Structured Span Prediction (2022)

Abstract: Named Entity Recognition (NER) is an important task in Natural Language Processing with applications in many domains. While the dominant paradigm of NER is sequence labelling, span-based approaches have become very popular in recent times but are less well understood. In this work, we study different aspects of span-based NER, namely the span representation, learning strategy, and decoding algorithms to avoid span overlap. We also propose an exact algorithm that efficiently finds the set of non-overlapping spans that maximizes a global score, given a list of candidate spans. We performed our study on three benchmark NER datasets from different domains. We make our code publicly available at https://github.com/urchade/span-structured-prediction .

## introduction named entity recognition (ner) is an important task in natural language processing whose goal is to identify and extract salient entities such as persons, organizations and locations from texts. ner systems are typically designed as sequence labelling: token-level prediction utilizing the bio scheme. while traditional approaches use hand-crafted features along with classical machine learning algorithms such as svms or decision trees @xcite , deep learning models learn features directly from the data using for example bi-directional lstms @xcite @xcite or more recently pre-trained language models such as bert @xcite . recently, span-based ner has gained in popularity. unlike sequence tagging which operates at the token level, span-based ner operates directly at the span level. the main idea is to enumerate all possible contiguous sequence of tokens of an input text and predict their identity @xcite . one of the major advantages of the span-based ner is that it can learn a rich representation of the span instead of only learning the representation of each token. in addition, a recent study by @xcite reveals that span-based ners are better in a context with more oov words and @xcite showed that span-based ners are much better than sequence labelling in settings with unlabelled entities (missing entities due to annotation errors). however, unlike sequence labelling, unconstrained span-based approaches tend to produce overlapping entities, which is undesirable for flat, non-overlapping ner tasks. to avoid overlap in span-based ner, two main approaches have been adopted in the literature. the first is the semi-markov conditional random field @xcite that trains a globally normalized model and then uses a viterbi algorithm to produce the optimal segmentation without span overlap, we call this approach semi-crf. the second algorithm is the one employed by @xcite for locally normalized span-based ner; it first eliminates all non-entity spans and deals with the overlap conflict by keeping the span with the highest prediction probability while eliminating the others. in this work, we call this approach greedy decoding. in this paper, we analyze and compare two formulations of span-based ner. the first is a segmentation model of the semi-crf; the second is the two-step pipeline of span filtering and decoding. in addition to greedy decoding, we propose an exact algorithm based on maximum weighted independent set (mwis) @xcite on internal graphs. we build such graphs to encode the overlapping structure between spans. this formulation of the ner task is novel up to our knowledge. for completeness, we include in the comparison a token-based sequence labeling model with a linear-chain crf. in order to understand the effect of span representation, we explore different alternatives includ-ing max-pooling, convolution and endpoints (representing span by its extreme tokens) and show that endpoints are effective across models and datasets. our contributions can be summarized as follow: our code for models and experiments is publicly available. 1 ## span representation given an input sequence @xmath0, . . . , x n ], a span (i, j) is the contiguous segment of tokens [x i , . . . , x j ]. the goal of representation is to compute an embedding vector for each span of an input text which can be used for downstream prediction tasks. we denote h @xmath1, j) with the width @xmath2; here d h , d @xmath3. the token representations are computed using a bert-based model @xcite . however, since bert-based tokenization divides the input words into subwords, we take the first subword to represent the whole word, which has proven to be very competitive for several token classification tasks @xcite . in the following, we present different approaches for representing the spans. endpoints this representation consists in representing a span using the representation of the tokens of its right and left extremities, in addition to a 1 anonymized for review. ## span scores we model the task of ner as assigning to each span (i, j) a label from a set of c different types that correspond to named-entity types and special null type, indicating that the span does not correspond to an entity. label assignment is constrained so that no pair of overlapping spans have entity types (both different from null). we present two models to solve this structured prediction problem: a locally normalized approach with a zero-order scoring function which does not take into consideration the interactions between label assignment ( §4); and a globally normalized approach with first-order scoring function which considers dependencies between pairs of consecutive spans ( §5). both formulations employ the following span scoring function. given a span representation s ij , the logits ϕ(i, j) ∈ r c for the c different labels are computed using a non-linear activation function followed by an affine transformation: ## locally normalized models under this approach, we perform span labeling in two steps, span classification followed by a decoding step. ## globally normalized model under this approach, ner is modeled using a semi-markov segmentation crf introduced by @xcite . the input sentence x is segmented into a labeled sequence of spans y. each segmentation is scored as: 3 with y @xmath4, j, l) being the labeled span at position k. unlike the scoring function in eq. 7, the score here contains the transition scores from label l ′ at position k -1 to label l, in the learnable matrix t . ## conclusion we investigated different span representations for ner and found that the endpoint representation is the most robust. moreover, we have proposed a new formulation of ner using overlapping graphs for which an exact and efficient decoding algorithm exists. we used the formulation to eliminate span overlap on locally trained models. finally, we conducted few-shot performance analysis for different modelling approaches and found that classical sequence labeling models provide strong results for datasets with few entity types, while span-based approaches are better for larger type sets.