Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n\^6) down to O(n\^3)
We introduce a novel chart-based algorithm for span-based parsing of discontinuous constituency trees of block degree two, including ill-nested structures. In particular, we show that we can build variants of our parser with smaller search spaces and time complexities ranging from O(n{\^{}}6) down to O(n{\^{}}3). The cubic time variant covers 98{\%} of constituents observed in linguistic treebanks while having the same complexity as continuous constituency parsers. We evaluate our approach on German and English treebanks (Negra, Tiger, and DPTB) and report state-of-the-art results in the fully supervised setting. We also experiment with pre-trained word embeddings and Bert-based neural networks.
Code (0)
등록된 구현이 없습니다.
Tasks
Constituency ParsingWord EmbeddingsSimilar Papers 제목 키워드 기반
Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3)
We introduce a novel chart-based algorithm for span-based parsing of discontinuous constituency trees of block degree two, including ill-nested structures. In particular, we show that we can build variants of our parser …
Constituency ParsingWord EmbeddingsDiscontinuous Constituency Parsing with a Stack-Free Transition System and a Dynamic Oracle
We introduce a novel transition system for discontinuous constituency parsing. Instead of storing subtrees in a stack --i.e. a data structure with linear-time sequential access-- the proposed system uses a set of parsing…
Constituency ParsingSentenceTree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsing
We address unsupervised discontinuous constituency parsing, where we observe a high variance in the performance of the only previous model in the literature. We propose to build an ensemble of different runs of the exist…
AllConstituency ParsingUnlexicalized Transition-based Discontinuous Constituency Parsing
Lexicalized parsing models are based on the assumptions that (i) constituents are organized around a lexical head (ii) bilexical statistics are crucial to solve ambiguities. In this paper, we introduce an unlexicalized t…
Constituency ParsingNeural Discontinuous Constituency Parsing
One of the most pressing issues in discontinuous constituency transition-based parsing is that the relevant information for parsing decisions could be located in any part of the stack or the buffer. In this paper, we pro…
Constituency Parsing