Spectral Unsupervised Parsing with Additive Tree Metrics

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 1062–1072, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics Spectral Unsupervised Parsing with Additive Tree Metrics Ankur P. Parikh School of Computer Science Carnegie Mellon University apparikh@cs.cmu.edu Shay B. Cohen School of Informatics University of Edinburgh scohen@inf.ed.ac.uk Eric P. Xing School of Computer Science Carnegie Mellon University epxing@cs.cmu.edu Abstract We propose a spectral approach for un- supervised constituent parsing that comes with theoretical guarantees on latent struc- ture recovery. Our approach is grammar- less – we directly learn the bracketing structure of a given sentence without us- ing a grammar model. The main algorithm is based on lifting the concept of additive tree metrics for structure learning of la- tent trees in the phylogenetic and machine learning communities to the case where the tree structure varies across examples. Although finding the “minimal” latent tree is NP-hard in general, for the case of pro- jective trees we find that it can be found using bilexical parsing algorithms. Empir- ically, our algorithm performs favorably compared to the constituent context model of Klein and Manning (2002) without the need for careful initialization. 1 Introduction Solutions to the problem of grammar induction have been long sought after since the early days of computational linguistics and are interesting both from cognitive and engineering perspectives. Cog- nitively, it is more plausible to assume that chil- dren obtain only terminal strings of parse trees and not the actual parse trees. This means the unsu- pervised setting is a better model for studying lan- guage acquisition. From the engineering perspec- tive, training data for unsupervised parsing exists in abundance (i.e. sentences and part-of-speech tags), and is much cheaper than the syntactically annotated data required for supervised training. Most existing solutions treat the problem of un- supervised parsing by assuming a generative pro- cess over parse trees e.g. probabilistic context free grammars (Jelinek et al., 1992), and the con- stituent context model (Klein and Manning, 2002). Learning then reduces to finding a set of parame- ters that are estimated by identifying a local max- imum of an objective function such as the likeli- hood (Klein and Manning, 2002) or a variant of it (Smith and Eisner, 2005; Cohen and Smith, 2009; Headden et al., 2009; Spitkovsky et al., 2010b; Gillenwater et al., 2010; Golland et al., 2012). Un- fortunately, finding the global maximum for these objective functions is usually intractable (Cohen and Smith, 2012) which often leads to severe lo- cal optima problems (but see Gormley and Eisner, 2013). Thus, strong experimental results are often achieved by initialization techniques (Klein and Manning, 2002; Gimpel and Smith, 2012), incre- mental dataset use (Spitkovsky et al., 2010a) and other specialized techniques to avoid local optima such as count transforms (Spitkovsky et al., 2013). These approaches, while empirically promising, generally lack theoretical justification. On the other hand, recently proposed spectral methods approach the problem via restriction of the PCFG model (Hsu et al., 2012) or matrix …

Content truncated to 500 words