Non-projective Dependency Parsing using Spanning Tree Algorithms
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))
Subscriber deck — free during early access
1 cards in “2.2.2 Projective Trees” · whole deck
2.2.2 Projective Trees
- How does the Eisner algorithm differ from Chu-Liu-Edmonds?It finds the maximum projective spanning tree in \(O(n^3)\) by bottom-up dynamic programming, which is needed to maintain the nested, non-crossing structure. Chu-Liu-Edmonds is greedy and recursive and needn’t enforce non-crossing.
- 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.2.2, p. 526
Source
- Ryan McDonald, Fernando Pereira, Kiril Ribarov and Jan Hajič. 2005. Non-projective Dependency Parsing using Spanning Tree Algorithms. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP 2005), pp. 523–530. https://aclanthology.org/H05-1066/