Faster Shift-Reduce Constituent Parsing with a Non-Binary, Bottom-Up Strategy 1footnote 11footnote 1© 2019. This is the final peer-reviewed manuscript that was accepted for publication at Artificial Intelligence and made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/. This may not reflect subsequent changes resulting from the publishing process such as editing, formatting, pagination, and other quality control mechanisms. The final journal publication is available at https://doi.org/10.1016/j.artint.2019.07.006.
Table 5: Comparison of parsing speed (sentences per second, sent./s.) and transition sequence length per sentence (tran./sent.) for the most common transition systems on WSJ §23, excluding time spent on un-binarization for the binary bottom-up parser.
['Parser', 'sent./s.', 'tran./sent.']
As expected, our parser is the fastest by a considerable margin, since all other transition systems need a longer transition sequence to perform the same task. Please note that times in decoding are dominated by neural network computations and a negligible fraction of total running time is consumed by the transition-based algorithm. Therefore, we can easily improve shift-reduce parsing performance by reducing the number of transitions, as this is what determines the number of times that the neural model is required for scoring, even if we undertake this by using an algorithm with quadratic worst-case time complexity.