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

被引：0
作者：
Corro, Caio [1 ]
机构：
[1] Univ Paris Saclay, CNRS, LISN, F-91400 Orsay, France
来源：
PROCEEDINGS OF THE 61ST ANNUAL MEETING OF THE ASSOCIATION FOR COMPUTATIONAL LINGUISTICS (ACL 2023): LONG PAPERS, VOL 1 | 2023年
关键词：
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
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 quadratictime 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.
引用
收藏
页码：10712 / 10724
页数：13
相关论文
共 51 条
[1]  
Alex B., 2007, TRANSLATIONAL CLIN L, P65
[2]  
[Anonymous], 2010, PARSING CONTEXT FREE
[3]  
Arora R, 2019, 57TH ANNUAL MEETING OF THE ASSOCIATION FOR COMPUTATIONAL LINGUISTICS (ACL 2019), P5862
[4]  
Cocke John, 1970, Tech. Rep.
[5]  
Corro C, 2020, PROCEEDINGS OF THE 2020 CONFERENCE ON EMPIRICAL METHODS IN NATURAL LANGUAGE PROCESSING (EMNLP), P2753
[6]  
Devlin J, 2019, 2019 CONFERENCE OF THE NORTH AMERICAN CHAPTER OF THE ASSOCIATION FOR COMPUTATIONAL LINGUISTICS: HUMAN LANGUAGE TECHNOLOGIES (NAACL HLT 2019), VOL. 1, P4171
[7]  
Doddington G. R., 2004, P 4 INT C LANG RES E
[8]  
Dozat Timothy, 2017, P INT C REPR LEARN I
[9]   AN EFFICIENT CONTEXT-FREE PARSING ALGORITHM [J].
EARLEY, J .
COMMUNICATIONS OF THE ACM, 1970, 13 (02) :94-&
[10]  
Finkel J., 2009, Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, V1, P141
123456