From Baby Steps to Leapfrog: How “Less is More” in Unsupervised Dependency Parsing

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 751–759, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics From Baby Steps to Leapfrog: How “Less is More” in Unsupervised Dependency Parsing∗ Valentin I. Spitkovsky Stanford University and Google Inc. valentin@cs.stanford.edu Hiyan Alshawi Google Inc., Mountain View, CA, 94043 hiyan@google.com Daniel Jurafsky Stanford University, Stanford, CA, 94305 jurafsky@stanford.edu Abstract We present three approaches for unsupervised grammar induction that are sensitive to data complexity and apply them to Klein and Man- ning’s Dependency Model with Valence. The first, Baby Steps, bootstraps itself via iterated learning of increasingly longer sentences and requires no initialization. This method sub- stantially exceeds Klein and Manning’s pub- lished scores and achieves 39.4% accuracy on Section 23 (all sentences) of the Wall Street Journal corpus. The second, Less is More, uses a low-complexity subset of the avail- able data: sentences up to length 15. Focus- ing on fewer but simpler examples trades off quantity against ambiguity; it attains 44.1% accuracy, using the standard linguistically- informed prior and batch training, beating state-of-the-art. Leapfrog, our third heuristic, combines Less is More with Baby Steps by mixing their models of shorter sentences, then rapidly ramping up exposure to the full train- ing set, driving up accuracy to 45.0%. These trends generalize to the Brown corpus; aware- ness of data complexity may improve other parsing models and unsupervised algorithms. 1 Introduction Unsupervised learning of hierarchical syntactic structure from free-form natural language text is a hard problem whose eventual solution promises to benefit applications ranging from question answer- ing to speech recognition and machine translation. A restricted version that targets dependencies and ∗Partially funded by NSF award IIS-0811974; first author supported by the Fannie & John Hertz Foundation Fellowship. assumes partial annotation, e.g., sentence bound- aries, tokenization and typically even part-of-speech (POS) tagging, has received much attention, elicit- ing a diverse array of techniques (Smith and Eis- ner, 2005; Seginer, 2007; Cohen et al., 2008). Klein and Manning’s (2004) Dependency Model with Va- lence (DMV) was the first to beat a simple parsing heuristic — the right-branching baseline. Today’s state-of-the-art systems (Headden et al., 2009; Co- hen and Smith, 2009) are still rooted in the DMV. Despite recent advances, unsupervised parsers lag far behind their supervised counterparts. Although large amounts of unlabeled data are known to im- prove semi-supervised parsing (Suzuki et al., 2009), the best unsupervised systems use less data than is available for supervised training, relying on complex models instead: Headden et al.’s (2009) Extended Valence Grammar (EVG) combats data sparsity with smoothing alone, training on the same small subset of the tree-bank as the classic implementation of the DMV; Cohen and Smith (2009) use more compli- cated algorithms (variational EM and MBR decod- ing) and stronger linguistic hints (tying related parts of speech and syntactically similar bilingual data). We explore what can be achieved through judi- cious use of data and simple, scalable techniques. Our first approach iterates over a series …

Content truncated to 500 words