A convex and feature-rich discriminative approach to dependency grammar induction

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1375–1384, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics A convex and feature-rich discriminative approach to dependency grammar induction ´Edouard Grave Columbia University edouard.grave@gmail.com No´emie Elhadad Columbia University noemie.elhadad@columbia.edu Abstract In this paper, we introduce a new method for the problem of unsupervised depen- dency parsing. Most current approaches are based on generative models. Learning the parameters of such models relies on solving a non-convex optimization prob- lem, thus making them sensitive to initial- ization. We propose a new convex formu- lation to the task of dependency grammar induction. Our approach is discriminative, allowing the use of different kinds of fea- tures. We describe an efficient optimiza- tion algorithm to learn the parameters of our model, based on the Frank-Wolfe algo- rithm. Our method can easily be general- ized to other unsupervised learning prob- lems. We evaluate our approach on ten languages belonging to four different fam- ilies, showing that our method is competi- tive with other state-of-the-art methods. 1 Introduction Grammar induction is an important problem in computational linguistics. Despite having recently received a lot of attention, it is still considered to be an unsolved problem. In this work, we are inter- ested in unsupervised dependency parsing. More precisely, our goal is to induce directed depen- dency trees, which capture binary syntactic rela- tions between the words of a sentence. Since our method is unsupervised, it does not have access to such syntactic structure and only take as in- put a corpus of words and their associated parts of speech. Most recent approaches to unsupervised depen- dency parsing are based on probabilistic genera- tive models, such as the dependency model with valence introduced by Klein and Manning (2004). Learning the parameters of such models is often All languages have their own grammar Figure 1: An example of dependency tree. done by maximizing the log-likelihood of unla- beled data, leading to a non-convex optimization problem. Thus, the performance of those methods rely heavily on the initialization, and practitioners have to find good heuristics to initialize their mod- els. In this paper, we describe a different approach to the problem of dependency grammar induction, inspired by discriminative clustering. We pro- pose to use a feature-rich discriminative parser, and to learn the parameters of this parser us- ing a convex quadratic objective function. In particular, this approach also allows us to in- duce non-projective dependency structures. Fol- lowing the work of Naseem et al. (2010), we use language-independent rules between pairs of parts-of-speech to guide our parser. More pre- cisely, we make the following contributions: • Our method is based on a feature-rich dis- criminative parser (section 3); • Learning the parameters of our parser is achieved using a convex objective, and is thus not sensitive to initialization (section 4); • Our method can produce non-projective de- pendency structures (section 3.2.2); • We propose an efficient algorithm …

Content truncated to 500 words