Spectral Learning for Non-Deterministic Dependency Parsing

Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 409–419, Avignon, France, April 23 - 27 2012. c⃝2012 Association for Computational Linguistics Spectral Learning for Non-Deterministic Dependency Parsing Franco M. Luque Universidad Nacional de C´ordoba and CONICET C´ordoba X5000HUA, Argentina francolq@famaf.unc.edu.ar Ariadna Quattoni and Borja Balle and Xavier Carreras Universitat Polit`ecnica de Catalunya Barcelona E-08034 {aquattoni,bballe,carreras}@lsi.upc.edu Abstract 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. 1 Introduction Dependency structures of natural language sen- tences exhibit a significant amount of non-local phenomena. Historically, there have been two main approaches to model non-locality: (1) in- creasing the order of the factors of a dependency model (e.g. with sibling and grandparent relations (Eisner, 2000; McDonald and Pereira, 2006; Car- reras, 2007; Martins et al., 2009; Koo and Collins, 2010)), and (2) using hidden states to pass in- formation across factors (Matsuzaki et al., 2005; Petrov et al., 2006; Musillo and Merlo, 2008). Higher-order models have the advantage that they are relatively easy to train, because estimat- ing the parameters of the model can be expressed as a convex optimization. However, they have two main drawbacks. (1) The number of param- eters grows significantly with the size of the fac- tors, leading to potential data-sparsity problems. A solution to address the data-sparsity problem is to explicitly tell the model what properties of higher-order factors need to be remembered. This can be achieved by means of feature engineering, but compressing such information into a state of bounded size will typically be labor intensive, and will not generalize across languages. (2) Increas- ing the size of the factors generally results in poly- nomial increases in the parsing cost. In principle, hidden variable models could solve some of the problems of feature engineering in higher-order factorizations, since they could automatically induce the information in a deriva- tion history that should be passed across factors. Potentially, they would require less feature engi- neering since they can learn from an annotated corpus an optimal way to compress derivations into hidden states. For example, one line of work has added hidden annotations to the non-terminals of a phrase-structure grammar (Matsuzaki et al., 2005; Petrov et al., 2006; Musillo and Merlo, 2008), resulting in compact grammars that ob- tain parsing accuracies comparable to lexicalized grammars. A second line of work has modeled hidden sequential structure, like in our case, but using PDFA (Infante-Lopez and de Rijke, 2004). Finally, a third line of work has induced hidden structure from the history of actions of a …

Content truncated to 500 words