Algorithms for Deterministic Incremental Dependency Parsing

6.3 Efficiency

1. What did Nivre find about learning and parsing times?
   Learning time is driven by the number of training instances, so the quadratic non-projective algorithm trained slowest. The projective list-based parser, though \(O(n^2)\) in the worst case, ran like the linear algorithms. Pseudo-projective parsers were always substantially slower to parse than their projective counterparts, sometimes slower than the non-projective parser.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §6.3, pp. 546–549
2. Why can a quadratic non-projective parser be faster than a linear-time pseudo-projective parser?
   Pseudo-projective parsing enlarges the label set, hence the number of SVM classes and binary classifiers, making every classification slower. For typical sentence lengths, this larger constant can outweigh the better asymptotic complexity. The pseudo-projective parsers were faster than the non-projective one on every data set with average sentence length above 18.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §6.3, pp. 546–549