mlsanityData to 7 Oct 2026

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

arXiv 2210.04738 ↗First posted 10 Oct 2022cs.CLcited by 3

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 15 of its 53 references that are in the map. First posted on arXiv 10 Oct 2022.

Builds on

15 of 53 references.

References · 15

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  2. 2015Rethinking the Inception Architecture for Computer Visioncited by 5,451
  3. 2016Deep Biaffine Attention for Neural Dependency Parsingcited by 334
  4. 2021A Unified Generative Framework for Various NER Subtaskscited by 141
  5. 2021Locate and Label: A Two-stage Identifier for Nested Named Entity Recognitioncited by 60
  6. 2017A Minimal Span-Based Neural Constituency Parsercited by 59
  7. 2018Differentiable Dynamic Programming for Structured Prediction and Attentioncited by 58
  8. 2021A Sequence-to-Set Network for Nested Named Entity Recognitioncited by 40
  9. 2019Nested Named Entity Recognition via Second-best Sequence Learning and Decodingcited by 34
  10. 2018Neural Segmental Hypergraphs for Overlapping Mention Recognitioncited by 32
  11. 2020Nested Named Entity Recognition with Partially-Observed TreeCRFscited by 23
  12. 2019Multi-Grained Named Entity Recognitioncited by 19
3 more
  1. 2018Labeling Gaps Between Words: Recognizing Overlapping Mentions with Mention Separatorscited by 14
  2. 2022Nested Named Entity Recognition as Latent Lexicalized Constituency Parsingcited by 14
  3. 2020Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3)cited by 11

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 2.

3 papers.

  1. 2024Named Entity Recognition Under Domain Shift via Metric Learning for Life Sciencescited by 2
  2. 2023Filtered Semi-Markov CRFcited by 1
  3. 2024Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsingcited by 0