Span-based discontinuous constituency parsing:a family of exact chart-based algorithms with time complexities from \mathcal{O}(n^{6}) down to \mathcal{O}(n^{3})
Table 3: Detailed discontinuous constituency parsing results for the fully supervised model.
['[EMPTY]', 'Negra D. recall', 'Negra D. prec.', 'Negra D. F1', 'Tiger D. recall', 'Tiger D. prec.', 'Tiger D. F1', 'DiscPTB D. recall', 'DiscPTB D. prec.', 'DiscPTB D. F1']
First, we observed that the O(n5) and O(n6) variants of our parsers produced exactly the same results in all settings. This may be expected as their cover of the original treebanks where almost similar. Second, surprisingly, the O(n3) parser produced better results in term of F-measure than other variants in all cases. We observe that while the O(n5) and O(n6) have an better recall than the O(n3) parser, their precision is drastically lower. This highlights a benefit of restricting the search space: the parser can retrieve less erroneous constituents leading to an improved overall precision.