A dynamic programming algorithm for span-based nested named-entity recognition in O(n2)

Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 10712–10724 July 9-14, 2023 ©2023 Association for Computational Linguistics A dynamic programming algorithm for span-based nested named-entity recognition in O(n2) Caio Corro Universite Paris-Saclay, CNRS, LISN, 91400, Orsay, France caio.corro@lisn.upsaclay.fr Abstract Span-based nested named-entity recognition (NER) has a cubic-time complexity using a variant 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 pro- posed algorithm covers a large part of three standard English benchmarks and delivers com- parable experimental results. 1 Introduction Named entity recognition (NER) is a fundamen- tal 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 proper- ties: 1. continuous, i.e. a mention corresponds to a contiguous sequence of words; 2. potentially nested, i.e. one mention can be inside another, but they can never partially overlap. Four examples are shown in Figure 1. In a span-based setting, recognition for nested NER has a cubic-time complexity (Finkel and Man- ning, 2009; Fu et al., 2021) using variants of the Cocke-Younger-Kasami (CYK) algorithm (Kasami, 1965; Younger, 1967; Cocke, 1970). If we re- strict the search space to non-nested mentions, then recognition can be realized in quadratic time using a semi-Markov model (Sarawagi and Cohen, 2004). An open question is whether it is possible to de- sign 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 com- plexity, 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 fol- low a trend in the syntactic parsing literature that studies search-spaces that allow the development of more efficient parsing algorithms, both for de- pendency and constituency structures (Pitler et al., 2012, 2013; Satta and Kuhlmann, 2013; Gómez- Rodríguez et al., 2010; Corro, 2020), inter alia. Our main contributions can be summarized as follows: • We present the semi-Markov and CYK-like models for non-nested and nested NER, re- spectively — although we do not claim that these approaches for NER are new, our pre- sentation of the CYK-like algorithm differs from previous work as it is tailored to the NER problem and guarantees uniqueness of deriva- tions; • We introduce a novel search space for nested NER that has no significant loss in coverage compared to the standard one, see Table 5; • We propose a novel quadratic-time recogni- tion algorithm for the aforementioned search space; • We experiment our quadratic-time algorithm on three English datasets (ACE-2004, ACE- 2005 and GENIA) …

Content truncated to 500 words