Exploiting Reducibility in Unsupervised Dependency Parsing

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 297–307, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Exploiting Reducibility in Unsupervised Dependency Parsing David Mareˇcek and Zdenˇek ˇZabokrtsk´y 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,zabokrtsky}@ufal.mff.cuni.cz Abstract The possibility of deleting a word from a sen- tence without violating its syntactic correct- ness belongs to traditionally known manifes- tations of syntactic dependency. We introduce a novel unsupervised parsing approach that is based on a new n-gram reducibility measure. We perform experiments across 18 languages available in CoNLL data and we show that our approach achieves better accuracy for the majority of the languages then previously re- ported results. 1 Introduction The true nature of the notion of dependency (af- ter removing sedimentary deposits of rules imposed only by more or less arbitrary conventions) remains still somewhat vague and elusive. This holds in spite of a seemingly strong background intuition and even after a decade of formalized large-scale dependency- based resources being available to the research com- munity. It is undeniable that a huge progress has been reached in the field of supervised dependency parsing, especially due to the CoNLL shared task se- ries. However, when it comes to unsupervised pars- ing, there are surprisingly few clues we could rely on. As mentioned e.g. by K¨ubler et al. (2009), one of the traditional linguistic criteria for recognizing de- pendency relations (including their head-dependent orientation) is that a head H of a construction C de- termines the syntactic category of C and can often replace C. Or, in words of Dependency Analysis by Reduction (Lopatkov´a et al., 2005), stepwise dele- tion of dependent elements within a sentence pre- serves its syntactic correctness. A similar idea of dependency analysis by splitting a sentence into all possible acceptable fragments is used by Gerdes and Kahane (2011). Of course, all the above works had to respond to the notorious fact that there are many language phe- nomena precluding the ideal (word by word) sen- tence reducibility (e.g. in the case of prepositional groups, or in the case of subjects in English finite clauses). However, we disregard their solutions ten- tatively and borrow only the very core of the re- ducibility idea: if a word can be removed from a sentence without damaging it, then it is likely to be dependent on some other (still present) word. As it is usual with dichotomies in natural lan- guages, it seems more adequate to use a continuous scale instead of the reducible-irreducible opposition. That is why we introduce a simple reducibility mea- sure based on n-gram corpus statistics. We employ this reducibility measure as the main feature in our unsupervised parsing procedure. The procedure is based on a commonly used Bayesian inference technique called Gibbs sampling (Gilks et al., 1996). In our sampler, the more re- ducible a given …

Content truncated to 500 words