Concavity and Initialization for Unsupervised Dependency Parsing

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 577–581, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Concavity and Initialization for Unsupervised Dependency Parsing Kevin Gimpel and Noah A. Smith Language Technologies Institute Carnegie Mellon University Pittsburgh, PA 15213, USA {kgimpel,nasmith}@cs.cmu.edu Abstract We investigate models for unsupervised learn- ing with concave log-likelihood functions. We begin with the most well-known example, IBM Model 1 for word alignment (Brown et al., 1993) and analyze its properties, dis- cussing why other models for unsupervised learning are so seldom concave. We then present concave models for dependency gram- mar induction and validate them experimen- tally. We find our concave models to be effec- tive initializers for the dependency model of Klein and Manning (2004) and show that we can encode linguistic knowledge in them for improved performance. 1 Introduction In NLP, unsupervised learning typically implies op- timization of a “bumpy” objective function riddled with local maxima. However, one exception is IBM Model 1 (Brown et al., 1993) for word alignment, which is the only model commonly used for unsu- pervised learning in NLP that has a concave log- likelihood function.1 For other models, such as those used in unsupervised part-of-speech tagging and grammar induction, and indeed for more sophis- ticated word alignment models, the log-likelihood function maximized by EM is non-concave. As a result, researchers are obligated to consider initial- ization in addition to model design (Klein and Man- ning, 2004; Goldberg et al., 2008). For example, consider the dependency grammar induction results shown in Table 1 when training the 1It is not strictly concave (Toutanova and Galley, 2011). widely used dependency model with valence (DMV; Klein and Manning, 2004). Using uniform distri- butions for initialization (UNIF) results in an accu- racy of 17.6% on the test set, well below the base- line of attaching each word to its right neighbor (ATTACHRIGHT, 31.7%). Furthermore, when using a set of 50 random initializers (RAND), the standard deviation of the accuracy is an alarming 8.3%. In light of this sensitivity to initialization, it is compelling to consider unsupervised models with concave log-likelihood functions, which may pro- vide stable, data-supported initializers for more complex models. In this paper, we explore the issues involved with such an expedition and elucidate the limitations of such models for unsupervised NLP. We then present simple concave models for depen- dency grammar induction that are easy to implement and offer efficient optimization. We also show how linguistic knowledge can be encoded without sacri- ficing concavity. Using our models to initialize the DMV, we find that they lead to an improvement in average accuracy across 18 languages. 2 IBM Model 1 and Concavity IBM Model 1 is a conditional model of a target- language sentence e of length m and an alignment a given a source-language sentence f of length l. The generation of m is assumed to occur with some (inconsequential) uniform probability ϵ. The align- ment vector a, a hidden …

Content truncated to 500 words