Using Left-corner Parsing to Encode Universal Structural Constraints in Grammar Induction

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 33–43, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Using Left-corner Parsing to Encode Universal Structural Constraints in Grammar Induction Hiroshi Noji Graduate School of Information Science Nara Institute of Science and Technology noji@is.naist.jp Yusuke Miyao National Institute of Informatics yusuke@nii.ac.jp Mark Johnson Department of Computing Macquarie University mark.johnson@mq.edu.au Abstract Center-embedding is difficult to process and is known as a rare syntactic construction across languages. In this paper we describe a method to incorporate this assumption into the gram- mar induction tasks by restricting the search space of a model to trees with limited center- embedding. The key idea is the tabulation of left-corner parsing, which captures the de- gree of center-embedding of a parse via its stack depth. We apply the technique to learn- ing of famous generative model, the depen- dency model with valence (Klein and Man- ning, 2004). Cross-linguistic experiments on Universal Dependencies show that often our method boosts the performance from the base- line, and competes with the current state-of- the-art model in a number of languages. 1 Introduction Human languages in the world are divergent, but they also exhibit many striking similarities (Green- berg, 1963; Hawkins, 2014). At the level of syn- tax, one attractive hypothesis for such regularities is that any grammars of languages have evolved un- der the pressures, or biases, to avoid structures that are difficult to process. For example it is known that many languages have a preference for shorter depen- dencies (Gildea and Temperley, 2010; Futrell et al., 2015), which originates from the difficulty in pro- cessing longer dependencies (Gibson, 2000). Such syntactic regularities can also be useful in applications, in particular in unsupervised (Klein and Manning, 2004; Mareˇcek and ˇZabokrtsk´y, 2012; Bisk and Hockenmaier, 2013) or weakly- supervised (Garrette et al., 2015) grammar induc- tion tasks, where the models try to recover the syn- tactic structure of language without access to the syntactically annotated data, e.g., from raw or part- of-speech tagged text only. In these settings, find- ing better syntactic regularities universal across lan- guages is essential, as they work as a small cue to the correct linguistic structures. A preference ex- ploited in many previous works is favoring shorter dependencies, which has been encoded in various ways, e.g., initialization of EM (Klein and Man- ning, 2004), or model parameters (Smith and Eis- ner, 2006), and this has been the key to success of learning (Gimpel and Smith, 2012). In this paper, we explore the utility for another universal syntactic bias that has not yet been ex- ploited in grammar induction: a bias against center- embedding. Center-embedding is a syntactic con- struction on which a clause is embedded into another one. An example is “The reporter [who the senator [who Mary met] attacked] ignored the president.”, where “who Mary met” is embedded in a larger relative clause. These constructions are known to cause memory overflow (Miller and Chomsky, 1963; Gibson, 2000), and also …

Content truncated to 500 words