Optimizing Spectral Learning for Parsing

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 1546–1556, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Optimizing Spectral Learning for Parsing Shashi Narayan and Shay B. Cohen School of Informatics University of Edinburgh Edinburgh, EH8 9LE, UK {snaraya2,scohen}@inf.ed.ac.uk Abstract We describe a search algorithm for opti- mizing the number of latent states when estimating latent-variable PCFGs with spectral methods. Our results show that contrary to the common belief that the number of latent states for each nontermi- nal in an L-PCFG can be decided in isola- tion with spectral methods, parsing results significantly improve if the number of la- tent states for each nonterminal is globally optimized, while taking into account in- teractions between the different nontermi- nals. In addition, we contribute an empiri- cal analysis of spectral algorithms on eight morphologically rich languages: Basque, French, German, Hebrew, Hungarian, Ko- rean, Polish and Swedish. Our results show that our estimation consistently per- forms better or close to coarse-to-fine expectation-maximization techniques for these languages. 1 Introduction Latent-variable probabilistic context-free gram- mars (L-PCFGs) have been used in the natural lan- guage processing community (NLP) for syntactic parsing for over a decade. They were introduced in the NLP community by Matsuzaki et al. (2005) and Prescher (2005), with Matsuzaki et al. us- ing the expectation-maximization (EM) algorithm to estimate them. Their performance on syntac- tic parsing of English at that stage lagged behind state-of-the-art parsers. Petrov et al. (2006) showed that one of the reasons that the EM algorithm does not estimate state-of-the-art parsing models for English is that the EM algorithm does not control well for the model size used in the parser – the number of la- tent states associated with the various nontermi- nals in the grammar. As such, they introduced a coarse-to-fine technique to estimate the grammar. It splits and merges nonterminals (with latent state information) with the aim to optimize the likeli- hood of the training data. Together with other types of fine tuning of the parsing model, this led to state-of-the-art results for English parsing. In more recent work, Cohen et al. (2012) de- scribed a different family of estimation algorithms for L-PCFGs. This so-called “spectral” family of learning algorithms is compelling because it offers a rigorous theoretical analysis of statistical conver- gence, and sidesteps local maxima issues that arise with the EM algorithm. While spectral algorithms for L-PCFGs are compelling from a theoretical perspective, they have been lagging behind in their empirical results on the problem of parsing. In this paper we show that one of the main reasons for that is that spectral algorithms require a more careful tuning proce- dure for the number of latent states than that which has been advocated for until now. In a sense, the relationship between our work and the work of Cohen et al. (2013) is analogous to the relation- ship between the work by Petrov et al. (2006) and the work by Matsuzaki et al. (2005): we suggest a …

Content truncated to 500 words