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