Punctuation: Making a Point in Unsupervised Dependency Parsing

Proceedings of the Fifteenth Conference on Computational Natural Language Learning, pages 19–28, Portland, Oregon, USA, 23–24 June 2011. c⃝2011 Association for Computational Linguistics Punctuation: Making a Point in Unsupervised Dependency Parsing Valentin I. Spitkovsky Computer Science Department Stanford University and Google Inc. valentin@cs.stanford.edu Hiyan Alshawi Google Inc. Mountain View, CA, 94043, USA hiyan@google.com Daniel Jurafsky Departments of Linguistics and Computer Science Stanford University, Stanford, CA, 94305, USA jurafsky@stanford.edu Abstract We show how punctuation can be used to im- prove unsupervised dependency parsing. Our linguistic analysis confirms the strong connec- tion between English punctuation and phrase boundaries in the Penn Treebank. However, approaches that naively include punctuation marks in the grammar (as if they were words) do not perform well with Klein and Manning’s Dependency Model with Valence (DMV). In- stead, we split a sentence at punctuation and impose parsing restrictions over its fragments. Our grammar inducer is trained on the Wall Street Journal (WSJ) and achieves 59.5% ac- curacy out-of-domain (Brown sentences with 100 or fewer words), more than 6% higher than the previous best results. Further evalu- ation, using the 2006/7 CoNLL sets, reveals that punctuation aids grammar induction in 17 of 18 languages, for an overall average net gain of 1.3%. Some of this improvement is from training, but more than half is from parsing with induced constraints, in inference. Punctuation-aware decoding works with exist- ing (even already-trained) parsing models and always increased accuracy in our experiments. 1 Introduction Unsupervised dependency parsing is a type of gram- mar induction — a central problem in computational linguistics. It aims to uncover hidden relations be- tween head words and their dependents in free-form text. Despite decades of significant research efforts, the task still poses a challenge, as sentence structure is underdetermined by only raw, unannotated words. Structure can be clearer in formatted text, which typically includes proper capitalization and punctua- tion (Gravano et al., 2009). Raw word streams, such as utterances transcribed by speech recognizers, are often difficult even for humans (Kim and Woodland, 2002). Therefore, one would expect grammar induc- ers to exploit any available linguistic meta-data. And yet in unsupervised dependency parsing, sentence- internal punctuation has long been ignored (Carroll and Charniak, 1992; Paskin, 2001; Klein and Man- ning, 2004; Blunsom and Cohn, 2010, inter alia). HTML is another kind of meta-data that is ordi- narily stripped out in pre-processing. However, re- cently Spitkovsky et al. (2010b) demonstrated that web markup can successfully guide hierarchical syntactic structure discovery, observing, for exam- ple, that anchors often match linguistic constituents: ..., whereas McCain is secure on the topic, Obama <a>[VP worries about winning the pro-Israel vote]</a>. We propose exploring punctuation’s potential to aid grammar induction. Consider a motivating ex- ample (all of our examples are from WSJ), in which all (six) marks align with constituent boundaries: [SBAR Although it probably has reduced the level of expenditures for some purchasers], [NP utilization man- agement] — [PP like most other cost containment strate- gies] — [VP doesn’t appear to have altered the …

Content truncated to 500 words