Experiments with Spectral Learning of Latent-Variable PCFGs

Proceedings of NAACL-HLT 2013, pages 148–157, Atlanta, Georgia, 9–14 June 2013. c⃝2013 Association for Computational Linguistics Experiments with Spectral Learning of Latent-Variable PCFGs Shay B. Cohen1, Karl Stratos1, Michael Collins1, Dean P. Foster2, and Lyle Ungar3 1Dept. of Computer Science, Columbia University 2Dept. of Statistics/3Dept. of Computer and Information Science, University of Pennsylvania {scohen,stratos,mcollins}@cs.columbia.edu, foster@wharton.upenn.edu, ungar@cis.upenn.edu Abstract Latent-variable PCFGs (L-PCFGs) are highly successful model for natural languagea parsing. Recent work (Cohen et al., 2012) has introduced a spectral algorithm for param- eter estimation of L-PCFGs, which—unlike the EM algorithm—is guaranteed to give con- sistent parameter estimates (it has PAC-style guarantees of sample complexity). This paper describes experiments using the spectral algo- rithm. We show that the algorithm provides models with the same accuracy as EM, but is an order of magnitude more efficient. We de- scribe a number of key steps used to obtain this level of performance; these should be rel- evant to other work on the application of spec- tral learning algorithms. We view our results as strong empirical evidence for the viability of spectral methods as an alternative to EM. 1 Introduction Latent-variable PCFGS (L-PCFGs) are a highly suc- cessful model for natural language parsing (Mat- suzaki et al., 2005; Petrov et al., 2006). Recent work (Cohen et al., 2012) has introduced a spectral learning algorithm for L-PCFGs. A crucial prop- erty of the algorithm is that it is guaranteed to pro- vide consistent parameter estimates—in fact it has PAC-style guarantees of sample complexity.1 This is in contrast to the EM algorithm, the usual method for parameter estimation in L-PCFGs, which has the weaker guarantee of reaching a local maximum of the likelihood function. The spectral algorithm is relatively simple and efficient, relying on a singular value decomposition of the training examples, fol- lowed by a single pass over the data where parame- ter values are calculated. Cohen et al. (2012) describe the algorithm, and the theory behind it, but as yet no experimental re- sults have been reported for the method. This paper 1under assumptions on certain singular values in the model; see section 2.3.1. describes experiments on natural language parsing using the spectral algorithm for parameter estima- tion. The algorithm provides models with slightly higher accuracy than EM (88.05% F-measure on test data for the spectral algorithm, vs 87.76% for EM), but is an order of magnitude more efficient (9h52m for training, compared to 187h12m, a speed-up of 19 times). We describe a number of key steps in obtain- ing this level of performance. A simple backed-off smoothing method is used to estimate the large num- ber of parameters in the model. The spectral algo- rithm requires functions mapping inside and outside trees to feature vectors—we make use of features corresponding to single level rules, and larger tree fragments composed of two or three levels of rules. We show that it is important to scale features by their inverse variance, in a manner that is closely related to methods used in canonical correlation analysis. Negative …

Content truncated to 500 words