Low-Rank Tensors for Scoring Dependency Structures

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 1381–1391, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics Low-Rank Tensors for Scoring Dependency Structures Tao Lei, Yu Xin, Yuan Zhang, Regina Barzilay, and Tommi Jaakkola Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology {taolei, yuxin, yuanzh, regina, tommi}@csail.mit.edu Abstract Accurate scoring of syntactic structures such as head-modifier arcs in dependency parsing typically requires rich, dimensional feature representations.high- small subset of such features is often se-A lected manually. This is problematic when features lack clear linguistic meaning as in embeddings or when the information is blended across features. In this paper, we use tensors to map high-dimensional fea- ture vectors into low dimensional repre- sentations. We explicitly maintain the pa- rameters as a low-rank tensor to obtain low dimensional representations of words in their syntactic roles, and to leverage mod- ularity in the tensor for easy training with online algorithms. Our parser consistently outperforms the Turbo and MST parsers across 14 different languages. We also ob- tain the best published UAS results on 5 languages.1 1 Introduction Finding an expressive representation of input sen- tences is crucial for accurate parsing. Syntac- tic relations manifest themselves in a broad range of surface indicators, ranging from morphological to lexical, including positional and part-of-speech (POS) tagging features. Traditionally, parsing re- search has focused on modeling the direct connec- tion between the features and the predicted syntac- tic relations such as head-modifier (arc) relations in dependency parsing. Even in the case of first- order parsers, this results in a high-dimensional vector representation of each arc. Discrete fea- tures, and their cross products, can be further com- plemented with auxiliary information about words 1Our code is available at https://github.com/ taolei87/RBGParser. participating in an arc, such as continuous vector representations of words. The exploding dimen- sionality of rich feature vectors must then be bal- anced with the difficulty of effectively learning the associated parameters from limited training data. A predominant way to counter the high dimen- sionality of features is to manually design or select a meaningful set of feature templates, which are used to generate different types of features (Mc- Donald et al., 2005a; Koo and Collins, 2010; Mar- tins et al., 2013). Direct manual selection may be problematic for two reasons. First, features may lack clear linguistic interpretation as in distribu- tional features or continuous vector embeddings of words. Second, designing a small subset of tem- plates (and features) is challenging when the rel- evant linguistic information is distributed across the features. For instance, morphological proper- ties are closely tied to part-of-speech tags, which in turn relate to positional features. These features are not redundant. Therefore, we may suffer a per- formance loss if we select only a small subset of the features. On the other hand, by including all the rich features, we face over-fitting problems. We depart from this view and leverage high- dimensional feature vectors by mapping them into low dimensional representations. We …

Content truncated to 500 words