A Provably Correct Learning Algorithm for Latent-Variable PCFGs

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 1052–1061, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics A Provably Correct Learning Algorithm for Latent-Variable PCFGs Shay B. Cohen School of Informatics University of Edinburgh scohen@inf.ed.ac.uk Michael Collins Department of Computer Science Columbia University mcollins@cs.columbia.edu Abstract We introduce a provably correct learning algorithm for latent-variable PCFGs. The algorithm relies on two steps: first, the use of a matrix-decomposition algorithm ap- plied to a co-occurrence matrix estimated from the parse trees in a training sample; second, the use of EM applied to a convex objective derived from the training sam- ples in combination with the output from the matrix decomposition. Experiments on parsing and a language modeling problem show that the algorithm is efficient and ef- fective in practice. 1 Introduction Latent-variable PCFGs (L-PCFGs) (Matsuzaki et al., 2005; Petrov et al., 2006) give state-of-the-art performance on parsing problems. The standard approach to parameter estimation in L-PCFGs is the EM algorithm (Dempster et al., 1977), which has the usual problems with local optima. Re- cent work (Cohen et al., 2012) has introduced an alternative algorithm, based on spectral methods, which has provable guarantees. Unfortunately this algorithm does not return parameter estimates for the underlying L-PCFG, instead returning the pa- rameter values up to an (unknown) linear trans- form. In practice, this is a limitation. We describe an algorithm that, like EM, re- turns estimates of the original parameters of an L- PCFG, but, unlike EM, does not suffer from prob- lems of local optima. The algorithm relies on two key ideas: 1) A matrix decomposition algorithm (sec- tion 5) which is applicable to matrices Q of the form Qf,g = � h p(h)p(f | h)p(g | h) where p(h), p(f | h) and p(g | h) are multinomial dis- tributions. This matrix form has clear relevance to latent variable models. We apply the matrix decomposition algorithm to a co-occurrence ma- trix that can be estimated directly from a training set consisting of parse trees without latent anno- tations. The resulting parameter estimates give us significant leverage over the learning problem. 2) Optimization of a convex objective function using EM. We show that once the matrix decom- position step has been applied, parameter estima- tion of the L-PCFG can be reduced to a convex optimization problem that is easily solved by EM. The algorithm provably learns the parameters of an L-PCFG (theorem 1), under an assumption that each latent state has at least one “pivot” feature. This assumption is similar to the “pivot word” as- sumption used by Arora et al. (2013) and Arora et al. (2012) in the context of learning topic models. We describe experiments on learning of L- PCFGs, and also on learning of the latent-variable language model of Saul and Pereira (1997). A hy- brid method, which uses our algorithm as an ini- tializer for EM, performs at the same accuracy as EM, but requires significantly fewer iterations for convergence: for example …

Content truncated to 500 words