Viterbi Training Improves Unsupervised Dependency Parsing

Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 9–17, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Viterbi Training Improves Unsupervised Dependency Parsing Valentin I. Spitkovsky Computer Science Department Stanford University and Google Inc. valentin@cs.stanford.edu Hiyan Alshawi Google Inc. Mountain View, CA, 94043, USA hiyan@google.com Daniel Jurafsky and Christopher D. Manning Departments of Linguistics and Computer Science Stanford University, Stanford, CA, 94305, USA jurafsky@stanford.edu and manning@cs.stanford.edu Abstract We show that Viterbi (or “hard”) EM is well-suited to unsupervised grammar in- duction. It is more accurate than standard inside-outside re-estimation (classic EM), significantly faster, and simpler. Our ex- periments with Klein and Manning’s De- pendency Model with Valence (DMV) at- tain state-of-the-art performance — 44.8% accuracy on Section 23 (all sentences) of the Wall Street Journal corpus — without clever initialization; with a good initial- izer, Viterbi training improves to 47.9%. This generalizes to the Brown corpus, our held-out set, where accuracy reaches 50.8% — a 7.5% gain over previous best results. We find that classic EM learns bet- ter from short sentences but cannot cope with longer ones, where Viterbi thrives. However, we explain that both algorithms optimize the wrong objectives and prove that there are fundamental disconnects be- tween the likelihoods of sentences, best parses, and true parses, beyond the well- established discrepancies between likeli- hood, accuracy and extrinsic performance. 1 Introduction Unsupervised learning is hard, often involving dif- ficult objective functions. A typical approach is to attempt maximizing the likelihood of unlabeled data, in accordance with a probabilistic model. Sadly, such functions are riddled with local op- tima (Charniak, 1993, Ch. 7, inter alia), since their number of peaks grows exponentially with in- stances of hidden variables. Furthermore, a higher likelihood does not always translate into superior task-specific accuracy (Elworthy, 1994; Merialdo, 1994). Both complications are real, but we will discuss perhaps more significant shortcomings. We prove that learning can be error-prone even in cases when likelihood is an appropriate mea- sure of extrinsic performance and where global optimization is feasible. This is because a key challenge in unsupervised learning is that the de- sired likelihood is unknown. Its absence renders tasks like structure discovery inherently under- constrained. Search-based algorithms adopt sur- rogate metrics, gambling on convergence to the “right” regularities in data. Their wrong objec- tives create cases in which both efficiency and per- formance improve when expensive exact learning techniques are replaced by cheap approximations. We propose using Viterbi training (Brown et al., 1993), instead of inside-outside re- estimation (Baker, 1979), to induce hierarchical syntactic structure from natural language text. Our experiments with Klein and Manning’s (2004) De- pendency Model with Valence (DMV), a popular state-of-the-art model (Headden et al., 2009; Co- hen and Smith, 2009; Spitkovsky et al., 2009), beat previous benchmark accuracies by 3.8% (on Section 23 of WSJ) and 7.5% (on parsed Brown). Since objective functions used in unsupervised grammar induction are provably wrong, advan- tages of exact inference may not apply. It makes sense to try the …

Content truncated to 500 words