A dynamic programming algorithm for span-based nested named-entity recognition in $O(n^2)$
Caio Corro
Anthology
Underline
Main: Syntax: Tagging, Chunking, and Parsing Main-poster Paper
Session 4: Syntax: Tagging, Chunking, and Parsing (Virtual Poster)
Conference Room: Pier 7&8
Conference Time: July 11, 11:00-12:30 (EDT) (America/Toronto)
Global Time: July 11, Session 4 (15:00-16:30 UTC)
Keywords:
parsing algorighms (symbolic, theoritical results)
TLDR:
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 ...
You can open the
#paper-P4008
channel in a separate window.
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 proposed algorithm covers a large part of three standard English benchmarks and delivers comparable experimental results.