Paper: Online Learning Of Approximate Dependency Parsing Algorithms

ACL ID E06-1011
Title Online Learning Of Approximate Dependency Parsing Algorithms
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 2006
Authors

In this paper we extend the maximum spanning tree (MST) dependency parsing framework of McDonald et al. (2005c) to incorporate higher-order feature rep- resentations and allow dependency struc- tures with multiple parents per word. We show that those extensions can make the MST framework computationally in- tractable, but that the intractability can be circumvented with new approximate pars- ing algorithms. We conclude with ex- periments showing that discriminative on- line learning using those approximate al- gorithms achieves the best reported pars- ing accuracy for Czech and Danish.