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 4: Total time in seconds to parse the full test sets: the nn column corresponds to the time taken by the forward pass of the neural network (maximum 5000 words per batch on a NVIDIA Tesla V100 SXM2 32 Go), each supplementary column is the time take by each variant of the chart-based algorithm (without any parallelization, one sentence at a time).
['[EMPTY]', 'nn', 'O( [ITALIC] n3)', 'O( [ITALIC] n4)', 'O( [ITALIC] n5), wn', 'O( [ITALIC] n5)', 'O( [ITALIC] n6), wn', 'O( [ITALIC] n6)']
In all cases, the runtime is reasonably fast and we do not need to remove long sentences. Interestingly, most of the time is spent for computing scores with the neural network with the cubic time parser, even if we use batches to benefit from the GPU architecture while our chart-based algorithm is not paralellized on CPU.