Paper: Spectral Learning for Non-Deterministic Dependency Parsing

ACL ID E12-1042
Title Spectral Learning for Non-Deterministic Dependency Parsing
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 2012

In this paper we study spectral learning methods for non-deterministic split head- automata grammars, a powerful hidden- state formalism for dependency parsing. We present a learning algorithm that, like other spectral methods, is efficient and non- susceptible to local minima. We show how this algorithm can be formulated as a technique for inducing hidden structure from distributions computed by forward- backward recursions. Furthermore, we also present an inside-outside algorithm for the parsing model that runs in cubic time, hence maintaining the standard pars- ing costs for context-free grammars.