A dynamic programming algorithm for span-based nested named-entity recognition in O(n^2)
This work addresses efficiency in natural language processing for researchers and practitioners, though it is incremental as it builds on existing methods.
The paper tackled the cubic-time complexity of span-based nested named-entity recognition by introducing a structural constraint to reduce it to quadratic-time, achieving comparable results on three standard English benchmarks.
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 proposed algorithm covers a large part of three standard English benchmarks and delivers comparable experimental results.