Unsupervised Dependency Parsing without Gold Part-of-Speech Tags

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1281–1290, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Unsupervised Dependency Parsing without Gold Part-of-Speech Tags Valentin I. Spitkovsky†∗ valentin@cs.stanford.edu Hiyan Alshawi∗ hiyan@google.com Angel X. Chang†∗ angelx@cs.stanford.edu Daniel Jurafsky‡† jurafsky@stanford.edu †Computer Science Department Stanford University Stanford, CA, 94305 ∗Google Research Google Inc. Mountain View, CA, 94043 ‡Department of Linguistics Stanford University Stanford, CA, 94305 Abstract We show that categories induced by unsuper- vised word clustering can surpass the perfor- mance of gold part-of-speech tags in depen- dency grammar induction. Unlike classic clus- tering algorithms, our method allows a word to have different tags in different contexts. In an ablative analysis, we first demonstrate that this context-dependence is crucial to the superior performance of gold tags — requir- ing a word to always have the same part-of- speech significantly degrades the performance of manual tags in grammar induction, elim- inating the advantage that human annotation has over unsupervised tags. We then introduce a sequence modeling technique that combines the output of a word clustering algorithm with context-colored noise, to allow words to be tagged differently in different contexts. With these new induced tags as input, our state-of- the-art dependency grammar inducer achieves 59.1% directed accuracy on Section 23 (all sentences) of the Wall Street Journal (WSJ) corpus — 0.7% higher than using gold tags. 1 Introduction Unsupervised learning — machine learning without manually-labeled training examples — is an active area of scientific research. In natural language pro- cessing, unsupervised techniques have been success- fully applied to tasks such as word alignment for ma- chine translation. And since the advent of the web, algorithms that induce structure from unlabeled data have continued to steadily gain importance. In this paper we focus on unsupervised part-of-speech tag- ging and dependency parsing — two related prob- lems of syntax discovery. Our methods are applica- ble to vast quantities of unlabeled monolingual text. Not all research on these problems has been fully unsupervised. For example, to the best of our knowl- edge, every new state-of-the-art dependency gram- mar inducer since Klein and Manning (2004) relied on gold part-of-speech tags. For some time, multi- point performance degradations caused by switching to automatically induced word categories have been interpreted as indications that “good enough” parts- of-speech induction methods exist, justifying the fo- cus on grammar induction with supervised part-of- speech tags (Bod, 2006), pace (Cramer, 2007). One of several drawbacks of this practice is that it weak- ens any conclusions that could be drawn about how computers (and possibly humans) learn in the ab- sence of explicit feedback (McDonald et al., 2011). In turn, not all unsupervised taggers actually in- duce word categories: Many systems — known as part-of-speech disambiguators (Merialdo, 1994) — rely on external dictionaries of possible tags. Our work builds on two older part-of-speech inducers — word clustering algorithms of Clark (2000) and Brown et al. (1992) — that were recently shown to be more robust than other well-known …

Content truncated to 500 words