A dynamic programming algorithm for span-based nested named-entity recognition in O(n^2) (2023)

Abstract: Span-based nested named-entity recognition (NER) has a cubic-time complexity using avariant of the CYK algorithm. We show that by adding a supplementary structural constraint on the search space, nested NER has a quadratic-time complexity, that is the same asymptotic complexity than the non-nested case. The proposed algorithm covers a large part of three standard English benchmarks and delivers comparable experimental results.

## introduction named entity recognition (ner) is a fundamental problem in information retrieval that aims to identify mentions of entities and their associated types in natural language documents. as such, the problem can be reduced to the identification and classification of segments of texts. in particular, we focus on mentions that have the following properties: four examples are shown in figure 1 . in a span-based setting, recognition for nested ner has a cubic-time complexity @xcite using variants of the cocke-younger-kasami (cyk) algorithm @xcite @xcite . if we restrict the search space to non-nested mentions, then recognition can be realized in quadratic time using a semi-markov model @xcite ). an open question is whether it is possible to design algorithms with better time-complexity/search space trade-offs. in this paper, we propose a novel span-based nested ner algorithm with a quadratic-time complexity, that is with the same time complexity as the semi-markov algorithm for the non-nested case. our approach is based on the observation that many mentions only contain at most one nested mention of length strictly greater than one. as such, we follow a trend in the syntactic parsing literature that studies search-spaces that allow the development of more efficient parsing algorithms, both for dependency and constituency structures @xcite @xcite @xcite , inter alia. our main contributions can be summarized as follows: tagging-based methods: ner can be reduced to a sentence tagging problem using bio and bilou schemes @xcite to bypass the quadratic-time complexity of semi-markov models. map inference (resp. marginal inference) is then a linear-time problem using the viterbi algorithm (resp. forward-backward algorithm). foot_0 however, this approach cannot incorporate span features neither be used for nested entities. @xcite and @xcite proposed to rely on several tagging layers to predict nested entities. @xcite introduced an extension of the viterbi algorithm that allows to rely on bio tagging for nested ner by considering second-best paths. to leverage the influence of outer entities, @xcite rely on different potential functions for inner entities. note that algorithms for the second-best paths method have a o(n 2 ) time complexity, that is similar to the span-based alogithm we propose. hypergraph-based methods: @xcite proposed an hypergraph-based method for nested ner. although this approach is appealing for its o(n) (approximate) inference algorithms, it suffers from two major issues: (1) the marginal inference algorithm overestimate the partition function; (2) the representation is ambiguous, that is a single path in the hypergraph may represent different analysis of the same sentence. muis and @xcite proposed a different hypergraph with o(n 2 ) inference algorithms that solves issue (1) but still exhibits issue (2). @xcite extended hypergraph methods to rely on neural network scoring. @xcite proposed a novel hypergraph method that fixes issues (1) and (2) but their approach does not forbid partially overlapping mentions. unstructured methods: several authors proposed to predict the presence of a mention on each span independently, sometimes with specialized neural architectures @xcite @xcite @xcite @xcite , inter alia. note that these approaches classify o(n 2 ) spans of text independently, hence the time-complexity is similar to the approach proposed in this paper but they cannot guarantee wellformedness of the prediction. ## nested named-entity recognition in this section, we introduce the nested ner problem and the vocabulary we use through the paper. ## related algorithms in this section, we present semi-markov and cyk-like algorithms for non-nested and nested ner, respectively. our presentation is based on the weighted logic programming formalism, also known as parsing-as-deduction (pereira and @xcite . we refer the reader to kallmeyer (2010, chapter 3) for an introduction to this formalism. the space and time complexities can be directly inferred by counting the maximum number of free variables in items and deduction rules, respectively. to the best of our knowledge, the presentation of the cyk-like algorithm is novel as previous work relied on the "actual" cyk algorithm @xcite or its variant for span-based syntactic parsing @xcite . ## o(n 2 ) nested named-entity recognition in this section, we describe our novel algorithm for quadratic-time nested named entity recognition. our algorithm limits its search space to mentions that contain at most one child of length strictly greater to one. items are of the following forms: axioms and goals are the same than the one of the cyk-like algorithm presented in section 4.2 -importantly, there is no extra axiom for items of the form [← , i, j]. for the moment, assume we restrict nested mentions that have a length strictly greater to the ones that share their left boundaries with their parent. we can re-use rules (d), (f), (g), (h) and (i) together with the following two deduction rules: we now extend the algorithm to the full targeted search space. the intuition is as follows: for a given mention, if it has a child mention of length strictly greater than one that does not share its left border with its parent, we first start recognizing this child mention and its left neighborhood and then move to right neighborhood using previously defined rules. we start the recognition of the left neighborhood using the two following rules: soundness and completeness can be proved by observing that, for a given mention, any children composition can be parsed with deduction rules as long as there is at most one child with a span strictly greater to one. moreover, these are the only children composition that can be recognized. finally, uniqueness of derivations can be proved as there is a single construction order of the internal structure of a mention. ## experimental results data. we evaluate our algorithms on the ace-2004 @xcite , @xcite and genia @xcite datasets. we split and pre-process the data using the tools distributed by @xcite . ## conclusion in this work, we proposed a novel quadratic-time parsing algorithm for nested ner, an asymptotic improvement of one order of magnitude over previously proposed span-based algorithms. we showed that the novel search-space has a good coverage of english datasets for nested ner. despite having the same time-complexity than semi-markov models, our approach achieves comparable experimental results to the cubic-time cyk-like algorithm. as such, we hope that our algorithm will be used as a drop-in fast replacement for future work in nested ner, where the cubic-time algorithm has often been qualified of slow. future work could consider the extension to lexicalized mentions.