Low-Rank Tensors for Scoring Dependency Structures

A great deal of parsing research has been dedicated to feature engineering [18, 25, 26]. While in most state-of-the-art parsers, features are selected manually [27, 29, 16, 22, 44, 35], automatic feature selection methods are gaining popularity [23, 1, 31, 2]. Following standard machine learning practices, these algorithms iteratively select a subset of features by optimizing parsing performance on a development set. These feature selection methods are particularly promising in parsing scenarios where the optimal feature set is likely to be a small subset of the original set of candidate features. Our technique, in contrast, is suitable for cases where the relevant information is distributed across a larger set of related features.

A lot of recent work has been done on mapping words into vector spaces [8, 41, 11, 30]. Traditionally, these vector representations have been derived primarily from co-occurrences of words within sentences, ignoring syntactic roles of the co-occurring words. Nevertheless, any such word-level representation can be used to offset inherent sparsity problems associated with full lexicalization [5]. In this sense they perform a role similar to POS tags.

Word-level vector space embeddings have so far had limited impact on parsing performance. From a computational perspective, adding non-sparse vectors directly as features, including their combinations, can significantly increase the number of active features for scoring syntactic structures (e.g., dependency arc). Because of this issue, Cirik and Şensoy (2013) used word vectors only as unigram features (without combinations) as part of a shift reduce parser [32]. The improvement on the overall parsing performance was marginal. Another application of word vectors is compositional vector grammar [36]. While this method learns to map word combinations into vectors, it builds on existing word-level vector representations. In contrast, we represent words as vectors in a manner that is directly optimized for parsing. This framework enables us to learn new syntactically guided embeddings while also leveraging separately estimated word vectors as starting features, leading to improved parsing performance.

Many machine learning problems can be cast as matrix problems where the matrix represents a set of co-varying parameters. Such problems include, for example, multi-task learning and collaborative filtering. Rather than assuming that each parameter can be set independently of others, it is helpful to assume that the parameters vary in a low dimensional subspace that has to be estimated together with the parameters. In terms of the parameter matrix, this corresponds to a low-rank assumption. Low-rank constraints are commonly used for improving generalization [19, 37, 38, 12]

A strict low-rank assumption can be restrictive. Indeed, recent approaches to matrix problems decompose the parameter matrix as a sum of low-rank and sparse matrices [40, 47]. The sparse matrix is used to highlight a small number of parameters that should vary independently even if most of them lie on a low-dimensional subspace [42, 4]. We follow this decomposition while extending the parameter matrix into a tensor.

Tensors are multi-way generalizations of matrices and possess an analogous notion of rank. Tensors are increasingly used as tools in spectral estimation [15], including in parsing [6] and other NLP problems [10], where the goal is to avoid local optima in maximum likelihood estimation. In contrast, we expand features for parsing into a multi-way tensor, and operate with an explicit low-rank representation of the associated parameter tensor. The explicit representation sidesteps inherent complexity problems associated with the tensor rank [14]. Our parameters are divided into a sparse set corresponding to manually chosen MST or Turbo parser features and a larger set governed by a low-rank tensor.

In an online learning setup, we update parameters successively based on each sentence. In order to apply the passive-aggressive algorithm, we fix two of $U$, $V$ and $W$ (say, for example, $V$ and $W$) in an alternating manner, and apply a closed-form update to the remaining parameters (here $U$ and $\theta$). This is possible since the objective function with respect to $\left(\theta ,U\right)$ has a similar form as in the original passive-aggressive algorithm. To illustrate this, consider a training sentence $x_i$. The update involves finding first the best competing tree,

which is the tree that violates the constraint in Eq. 4 most (i.e. maximizes the loss ${\xi }_i$). We then obtain parameter increments $\mathrm{\Delta }\theta$ and $\mathrm{\Delta }U$ by solving

In this way, the optimization problem attempts to keep the parameter change as small as possible, while forcing it to achieve mostly zero loss on this single instance. This problem has a closed form solution

where

where ${\left(u\odot v\right)}_i=u_i{v}_i$ is the Hadamard (element-wise) product. The magnitude of change of $\theta$ and $U$ is controlled by the parameter $C$. By varying $C$, we can determine an appropriate step size for the online updates. The updates also illustrate how $\gamma$ balances the effect of the MST component of the score relative to the low-rank tensor score. When $\gamma =0$, the arc scores are entirely based on the low-rank tensor and $\mathrm{\Delta }\theta =0$. Note that ${\varphi }_h$, ${\varphi }_m$, ${\varphi }_{h,m}$, and ${\varphi }_{h\to m}$ are typically very sparse for each word or arc. Therefore $du$ and $d\theta$ are also sparse and can be computed efficiently.

The alternating online algorithm relies on how we initialize $U$, $V$, and $W$ since each update is carried out in the context of the other two. A random initialization of these parameters is unlikely to work well, both due to the dimensions involved, and the nature of the alternating updates. We consider here instead a reasonable deterministic “guess” as the initialization method.

We begin by training our model without any low-rank parameters, and obtain parameters $\theta$. The majority of features in this MST component can be expressed as elements of the feature tensor, i.e., as ${\left[{\varphi }_h\otimes {\varphi }_m\otimes {\varphi }_{h,m}\right]}_{i,j,k}$. We can therefore create a tensor representation of $\theta$ such that $B_{i,j,k}$ equals the corresponding parameter value in $\theta$. We use a low-rank version of $B$ as the initialization. Specifically, we unfold the tensor B into a matrix $B^{\left(h\right)}$ of dimensions $n$ and $nd$, where $n=dim\left({\varphi }_h\right)=dim\left({\varphi }_m\right)$ and $d=dim\left({\varphi }_{h,m}\right)$. For instance, a rank-1 tensor can be unfolded as $u\otimes v\otimes w=u\otimes \text{vec}\left(v\otimes w\right)$. We compute the top-r SVD of the resulting unfolded matrix such that $B^{\left(h\right)}=P^{T}SQ$. $U$ is initialized as $P$. Each right singular vector $S_{i}Q\left(i,:\right)$ is also a matrix in ${ℝ}^{n\times d}$. The leading left and right singular vectors of this matrix are assigned to $V\left(i,:\right)$ and $W\left(i,:\right)$ respectively. In our implementation, we run one epoch of our model without low-rank parameters and initialize the tensor $A$.

The passive-aggressive algorithm regularizes the increments (e.g. $\mathrm{\Delta }\theta$ and $\mathrm{\Delta }U$) during each update but does not include any overall regularization. In other words, keeping updating the model may lead to large parameter values and over-fitting. To counter this effect, we use parameter averaging as used in the MST and Turbo parsers. The final parameters are those averaged across all the iterations (cf. [7]). For simplicity, in our algorithm we average $U$, $V$, $W$ and $\theta$ separately, which works well empirically.

We test our dependency model on 14 languages, including the English dataset from CoNLL 2008 shared tasks and all 13 datasets from CoNLL 2006 shared tasks [3, 39]. These datasets include manually annotated dependency trees, POS tags and morphological information. Following standard practices, we encode this information as features.

We compare our model to MST and Turbo parsers on non-projective dependency parsing. For our parser, we train both a first-order parsing model (as described in Section 3 and 4) as well as a third-order model. The third order parser simply adds high-order features, those typically used in MST and Turbo parsers, into our scoring component. The decoding algorithm for the third-order parsing is based on [46]. For the Turbo parser, we directly compare with the recent published results in [22]. For the MST parser, we train and test using the most recent version of the code.⁴⁴http://sourceforge.net/projects/mstparser/ In addition, we implemented two additional baselines, NT-1st (first order) and NT-3rd (third order), corresponding to our model without the tensor component.

For the arc feature vector ${\varphi }_{h\to m}$, we use the same set of feature templates as MST v0.5.1. For head/modifier vector ${\varphi }_h$ and ${\varphi }_m$, we show the complete set of feature templates used by our model in Table 1. Finally, we use a similar set of feature templates as Turbo v2.1 for 3rd order parsing.

To add auxiliary word vector representations, we use the publicly available word vectors [5], learned from raw data [13, 20]. Three languages in our dataset – English, German and Swedish – have corresponding word vectors in this collection.⁵⁵https://github.com/wolet/sprml13-word-embeddings The dimensionality of this representation varies by language: English has 50 dimensional word vectors, while German and Swedish have 25 dimensional word vectors. Each entry of the word vector is added as a feature value into feature vectors ${\varphi }_h$ and ${\varphi }_m$. For each word in the sentence, we add its own word vector as well as the vectors of its left and right words.

We should note that since our model parameter $A$ is represented and learned in the low-rank form, we only have to store and maintain the low-rank projections $U{\varphi }_h$, $V{\varphi }_m$ and $W{\varphi }_{h,m}$ rather than explicitly calculate the feature tensor ${\varphi }_h\otimes {\varphi }_m\otimes {\varphi }_{h,m}$. Therefore updating parameters and decoding a sentence is still efficient, i.e., linear in the number of values of the feature vector. In contrast, assume we take the cross-product of the auxiliary word vector values, POS tags and lexical items of a word and its context, and add the crossed values into a normal model (in ${\varphi }_{h\to m}$). The number of features for each arc would be at least quadratic, growing into thousands, and would be a significant impediment to parsing efficiency.

Following standard practices, we train our full model and the baselines for 10 epochs. As the evaluation measure, we use unlabeled attachment scores (UAS) excluding punctuation. In all the reported experiments, the hyper-parameters are set as follows: $r=50$ (rank of the tensor), $C=1$ for first-order model and $C=0.01$ for third-order model.

Table 2 shows the performance of our model and the baselines on 14 CoNLL datasets. Our model outperforms Turbo parser, MST parser, as well as its own variants without the tensor component. The improvements of our low-rank model are consistent across languages: results for the first order parser are better on 11 out of 14 languages. By comparing NT-1st and NT-3rd (models without low-rank) with our full model (with low-rank), we obtain 0.7% absolute improvement on first-order parsing, and 0.3% improvement on third-order parsing. Our model also achieves the best UAS on 5 languages.

We next focus on the first-order model and gauge the impact of the tensor component. First, we test our model by varying the hyper-parameter $\gamma$ which balances the tensor score and the traditional MST/Turbo score components. Figure 1 shows the average UAS on CoNLL test datasets after each training epoch. We can see that the improvement of adding the low-rank tensor is consistent across various choices of hyper parameter $\gamma$. When training with the tensor component alone ($\gamma =0$), the model converges more slowly. Learning of the tensor is harder because the scoring function is not linear (nor convex) with respect to parameters $U$, $V$ and $W$. However, the tensor scoring component achieves better generalization on the test data, resulting in better UAS than NT-1st after 8 training epochs.

To assess the ability of our model to incorporate a range of features, we add unsupervised word vectors to our model. As described in previous section, we do so by appending the values of different coordinates in the word vector into ${\varphi }_h$ and ${\varphi }_m$. As Table 3 shows, adding this information increases the parsing performance for all the three languages. For instance, we obtain more than 0.5% absolute improvement on Swedish.

Since our model learns a compressed representation of feature vectors, we are interested to measure its performance when part-of-speech tags are not provided (See Table 4). The rationale is that given all other features, the model would induce representations that play a similar role to POS tags. Note that the performance of traditional parsers drops when tags are not provided. For example, the performance gap is 10% on German. Our experiments show that low-rank parser operates effectively in the absence of tags. In fact, it nearly reaches the performance of the original parser that used the tags on English.

We manually analyze low-dimensional projections to assess whether they capture syntactic abstraction. For this purpose, we train a model with only a tensor component (such that it has to learn an accurate tensor) on the English dataset and obtain low dimensional embeddings $U{\varphi }_w$ and $V{\varphi }_w$ for each word. The two r-dimension vectors are concatenated as an “averaged” vector. We use this vector to calculate the cosine similarity between words. Table 5 shows examples of five closest neighbors of queried words. While these lists include some noise, we can clearly see that the neighbors exhibit similar syntactic behavior. For example, “on” is close to other prepositions. More interestingly, we can consider the impact of syntactic context on the derived projections. The bottom part of Table 5 shows that the neighbors change substantially depending on the syntactic role of the word. For example, the closest words to the word “increase” are verbs in the context phrase “will increase again”, while the closest words become nouns given a different phrase “an increase of”.

Table 6 illustrates the impact of estimating low-rank tensor parameters on the running time of the algorithm. For comparison, we also show the NT-1st times across three typical languages. The Arabic dataset has the longest average sentence length, while the Chinese dataset has the shortest sentence length in CoNLL 2006. Based on these results, estimating a rank-50 tensor together with MST parameters only increases the running time by a factor of 1.7.