Improving Unsupervised Dependency Parsing with Richer Contexts and Smoothing

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 101–109, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Improving Unsupervised Dependency Parsing with Richer Contexts and Smoothing William P. Headden III, Mark Johnson, David McClosky Brown Laboratory for Linguistic Information Processing (BLLIP) Brown University Providence, RI 02912 {headdenw,mj,dmcc}@cs.brown.edu Abstract Unsupervised grammar induction models tend to employ relatively simple models of syntax when compared to their supervised counter- parts. Traditionally, the unsupervised mod- els have been kept simple due to tractabil- ity and data sparsity concerns. In this paper, we introduce basic valence frames and lexi- cal information into an unsupervised depen- dency grammar inducer and show how this additional information can be leveraged via smoothing. Our model produces state-of-the- art results on the task of unsupervised gram- mar induction, improving over the best previ- ous work by almost 10 percentage points. 1 Introduction The last decade has seen great strides in statisti- cal natural language parsing. Supervised and semi- supervised methods now provide highly accurate parsers for a number of languages, but require train- ing from corpora hand-annotated with parse trees. Unfortunately, manually annotating corpora with parse trees is expensive and time consuming so for languages and domains with minimal resources it is valuable to study methods for parsing without re- quiring annotated sentences. In this work, we focus on unsupervised depen- dency parsing. Our goal is to produce a directed graph of dependency relations (e.g. Figure 1) where each edge indicates a head-argument relation. Since the task is unsupervised, we are not given any ex- amples of correct dependency graphs and only take words and their parts of speech as input. Most of the recent work in this area (Smith, 2006; Co- hen et al., 2008) has focused on variants of the The big dog barks Figure 1: Example dependency parse. Dependency Model with Valence (DMV) by Klein and Manning (2004). DMV was the first unsu- pervised dependency grammar induction system to achieve accuracy above a right-branching baseline. However, DMV is not able to capture some of the more complex aspects of language. Borrowing some ideas from the supervised parsing literature, we present two new models: Extended Valence Gram- mar (EVG) and its lexicalized extension (L-EVG). The primary difference between EVG and DMV is that DMV uses valence information to determine the number of arguments a head takes but not their cat- egories. In contrast, EVG allows different distri- butions over arguments for different valence slots. L-EVG extends EVG by conditioning on lexical in- formation as well. This allows L-EVG to potentially capture subcategorizations. The downside of adding additional conditioning events is that we introduce data sparsity problems. Incorporating more valence and lexical information increases the number of pa- rameters to estimate. A common solution to data sparsity in supervised parsing is to add smoothing. We show that smoothing can be employed in an un- supervised fashion as well, and show that mixing DMV, EVG, and L-EVG together produces state-of- the-art …

Content truncated to 500 words