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.- Anthology ID:
- 2023.acl-long.598
- Volume:
- Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
- Month:
- July
- Year:
- 2023
- Address:
- Toronto, Canada
- Editors:
- Anna Rogers, Jordan Boyd-Graber, Naoaki Okazaki
- Venue:
- ACL
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 10712–10724
- Language:
- URL:
- https://aclanthology.org/2023.acl-long.598
- DOI:
- 10.18653/v1/2023.acl-long.598
- Cite (ACL):
- Caio Corro. 2023. A dynamic programming algorithm for span-based nested named-entity recognition in O(n2). In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 10712–10724, Toronto, Canada. Association for Computational Linguistics.
- Cite (Informal):
- A dynamic programming algorithm for span-based nested named-entity recognition in O(n2) (Corro, ACL 2023)
- PDF:
- https://preview.aclanthology.org/ingest-bitext-workshop/2023.acl-long.598.pdf