Spectral Dependency Parsing with Latent Variables

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 205–213, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Spectral Dependency Parsing with Latent Variables Paramveer S. Dhillon1, Jordan Rodu2, Michael Collins3, Dean P. Foster2 and Lyle H. Ungar1 1Computer & Information Science/ 2Statistics, University of Pennsylvania, Philadelphia, PA, U.S.A 3 Computer Science, Columbia University, New York, NY, U.S.A {dhillon|ungar@cis.upenn.edu}, {jrodu|foster@wharton.upenn.edu} mcollins@cs.columbia.edu Abstract Recently there has been substantial interest in using spectral methods to learn generative se- quence models like HMMs. Spectral meth- ods are attractive as they provide globally con- sistent estimates of the model parameters and are very fast and scalable, unlike EM meth- ods, which can get stuck in local minima. In this paper, we present a novel extension of this class of spectral methods to learn depen- dency tree structures. We propose a simple yet powerful latent variable generative model for dependency parsing, and a spectral learn- ing method to efficiently estimate it. As a pi- lot experimental evaluation, we use the spec- tral tree probabilities estimated by our model to re-rank the outputs of a near state-of-the- art parser. Our approach gives us a moderate reduction in error of up to 4.6% over the base- line re-ranker. 1 Introduction Markov models have been for two decades a workhorse of statistical pattern recognition with ap- plications ranging from speech to vision to lan- guage. Adding latent variables to these models gives us additional modeling power and have shown suc- cess in applications like POS tagging (Merialdo, 1994), speech recognition (Rabiner, 1989) and ob- ject recognition (Quattoni et al., 2004). However, this comes at the cost that the resulting parameter estimation problem becomes non-convex and tech- niques like EM (Dempster et al., 1977) which are used to estimate the parameters can only lead to lo- cally optimal solutions. Recent work by Hsu et al. (2008) has shown that globally consistent estimates of the parameters of HMMs can be found by using spectral methods, par- ticularly by singular value decomposition (SVD) of appropriately defined linear systems. They avoid the NP Hard problem of the global optimization prob- lem of the HMM parameters (Terwijn, 2002), by putting restrictions on the smallest singular value of the HMM parameters. The main intuition be- hind the model is that, although the observed data (i.e. words) seem to live in a very high dimensional space, but in reality they live in a very low dimen- sional space (size k ∼ 30 − 50) and an appropriate eigen decomposition of the observed data will re- veal the underlying low dimensional dynamics and thereby revealing the parameters of the model. Be- sides ducking the NP hard problem, the spectral methods are very fast and scalable to train compared to EM methods. In this paper we generalize the approach of Hsu et al. (2008) to learn dependency tree structures with latent variables.1 Petrov et al. (2006) and Musillo and Merlo (2008) have shown that …

Content truncated to 500 words