Stop-probability estimates computed on a large corpus improve Unsupervised Dependency Parsing

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 281–290, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Stop-probability estimates computed on a large corpus improve Unsupervised Dependency Parsing David Mareˇcek and Milan Straka Charles University in Prague, Faculty of Mathematics and Physics Institute of Formal and Applied Linguistics Malostransk´e n´amˇest´ı 25, 11800 Prague, Czech Republic {marecek,straka}@ufal.mff.cuni.cz Abstract Even though the quality of unsupervised dependency parsers grows, they often fail in recognition of very basic dependencies. In this paper, we exploit a prior knowledge of STOP-probabilities (whether a given word has any children in a given direc- tion), which is obtained from a large raw corpus using the reducibility principle. By incorporating this knowledge into Depen- dency Model with Valence, we managed to considerably outperform the state-of-the- art results in terms of average attachment score over 20 treebanks from CoNLL 2006 and 2007 shared tasks. 1 Introduction The task of unsupervised dependency parsing (which strongly relates to the grammar induction task) has become popular in the last decade, and its quality has been greatly increasing during this period. The first implementation of Dependency Model with Valence (DMV) (Klein and Manning, 2004) with a simple inside-outside inference algo- rithm (Baker, 1979) achieved 36% attachment score on English and was the first system outper- forming the adjacent-word baseline.1 Current attachment scores of state-of-the-art un- supervised parsers are higher than 50% for many languages (Spitkovsky et al., 2012; Blunsom and Cohn, 2010). This is still far below the super- vised approaches, but their indisputable advan- tage is the fact that no annotated treebanks are needed and the induced structures are not bur- dened by any linguistic conventions. Moreover, 1The adjacent-word baseline is a dependency tree in which each word is attached to the previous (or the follow- ing) word. The attachment score of 35.9% on all the WSJ test sentences was taken from (Blunsom and Cohn, 2010). supervised parsers always only simulate the tree- banks they were trained on, whereas unsupervised parsers have an ability to be fitted to different par- ticular applications. Some of the current approaches are based on the DMV, a generative model where the gram- mar is expressed by two probability distributions: Pchoose(cd|ch, dir), which generates a new child cd attached to the head ch in the direction dir (left or right), and Pstop(STOP|ch, dir, · · · ), which makes a decision whether to generate another child of ch in the direction dir or not.2 Such a grammar is then inferred using sampling or varia- tional methods. Unfortunately, there are still cases where the in- ferred grammar is very different from the gram- mar we would expect, e.g. verbs become leaves instead of governing the sentences. Rasooli and Faili (2012) and Bisk and Hockenmaier (2012) made some efforts to boost the verbocentricity of the inferred structures; however, both of the ap- proaches require manual identification of the POS tags marking the verbs, which renders them use- less when unsupervised POS tags are …

Content truncated to 500 words