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

Our main contributions can be summarized as Named entity recognition (NER) is a fundamental follows: problem in information retrieval that aims to identify We present the semi-Markov and CYK-like mentions of entities and their associated types models for non-nested and nested NER, respectively in natural language documents. As such, the problem -- although we do not claim that can be reduced to the identification and classification these approaches for NER are new, our presentation of segments of texts. In particular, we of the CYK-like algorithm differs focus on mentions that have the following properties: from previous work as it is tailored to the NER problem and guarantees uniqueness of 1. continuous, i.e. a mention corresponds to a derivations; contiguous sequence of words; We introduce a novel search space for nested 2. potentially nested, i.e. one mention can be inside NER that has no significant loss in coverage another, but they can never partially overlap.