Non-projective Dependency Parsing using Spanning Tree Algorithms

2.3 Dependency Trees as MSTs: Summary

1. Why is non-projective parsing “easier” than projective parsing in the MST framework?
   Non-projective parsing searches all spanning trees with no non-crossing constraint, which takes \(O(n^2)\) with Chu-Liu-Edmonds; enforcing projectivity needs Eisner’s \(O(n^3)\) dynamic program. This dispels the notion that non-projective parsing is harder.
   • McDonald et al., 2005, Non-projective Dependency Parsing using Spanning Tree Algorithms (Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP 2005)), §2.3, pp. 526–527
2. How does MST parsing differ from pseudo-projective parsing (Nivre and Nilsson 2005)?
   Pseudo-projective parsing parses projectively and recovers non-projective edges through learned edge transformations. MST parsing is true non-projective parsing: it searches the full space of non-projective trees exactly and efficiently, without pruning.
   • McDonald et al., 2005, Non-projective Dependency Parsing using Spanning Tree Algorithms (Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP 2005)), §2.3, pp. 526–527