Online Learning in Tensor Space

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 666–675, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics Online Learning in Tensor Space Yuan Cao Sanjeev Khudanpur Center for Language & Speech Processing and Human Language Technology Center of Excellence The Johns Hopkins University Baltimore, MD, USA, 21218 {yuan.cao, khudanpur}@jhu.edu Abstract We propose an online learning algorithm based on tensor-space models. A tensor- space model represents data in a compact way, and via rank-1 approximation the weight tensor can be made highly struc- tured, resulting in a significantly smaller number of free parameters to be estimated than in comparable vector-space models. This regularizes the model complexity and makes the tensor model highly effective in situations where a large feature set is de- fined but very limited resources are avail- able for training. We apply with the pro- posed algorithm to a parsing task, and show that even with very little training data the learning algorithm based on a ten- sor model performs well, and gives signif- icantly better results than standard learn- ing algorithms based on traditional vector- space models. 1 Introduction Many NLP applications use models that try to in- corporate a large number of linguistic features so that as much human knowledge of language can be brought to bear on the (prediction) task as pos- sible. This also makes training the model param- eters a challenging problem, since the amount of labeled training data is usually small compared to the size of feature sets: the feature weights cannot be estimated reliably. Most traditional models are linear models, in the sense that both the features of the data and model parameters are represented as vectors in a vector space. Many learning algorithms applied to NLP problems, such as the Perceptron (Collins, 2002), MIRA (Crammer et al., 2006; McDonald et al., 2005; Chiang et al., 2008), PRO (Hop- kins and May, 2011), RAMPION (Gimpel and Smith, 2012) etc., are based on vector-space mod- els. Such models require learning individual fea- ture weights directly, so that the number of param- eters to be estimated is identical to the size of the feature set. When millions of features are used but the amount of labeled data is limited, it can be dif- ficult to precisely estimate each feature weight. In this paper, we shift the model from vector- space to tensor-space. Data can be represented in a compact and structured way using tensors as containers. Tensor representations have been ap- plied to computer vision problems (Hazan et al., 2005; Shashua and Hazan, 2005) and information retrieval (Cai et al., 2006a) a long time ago. More recently, it has also been applied to parsing (Cohen and Collins, 2012; Cohen and Satta, 2013) and se- mantic analysis (Van de Cruys et al., 2013). A linear tensor model represents both features and weights in tensor-space, hence the weight tensor can be factorized and approximated by a linear sum of rank-1 tensors. This low-rank approxi- mation imposes structural constraints …

Content truncated to 500 words