Unsupervised Dependency Parsing with Transferring
Distribution via Parallel Guidance and Entropy Regularization

In this paper, we will use the following notation: $𝒙$ represents a generic input sentence, and $𝒚$ represents a generic dependency tree. $\mathrm{T}\left(𝒙\right)$ is used to denote the set of possible dependency trees for sentence $𝒙$. The probabilistic model for dependency parsing defines a family of conditional probability $p_{\lambda }\left(𝒚\right|𝒙)$ over all $𝒚$ given sentence $𝒙$, with a log-linear form:

where $F_j$ are feature functions, $\lambda =\left({\lambda }_1,{\lambda }_2,\mathrm{\dots }\right)$ are parameters of the model, and $Z\left(𝒙\right)$ is a normalization factor, which is commonly referred to as the partition function:

A common strategy to make this parsing model efficiently computable is to factor dependency trees into sets of edges:

That is, dependency tree $y$ is treated as a set of edges $e$ and each feature function $F_j\left(𝒚,𝒙\right)$ is equal to the sum of all the features $f_j\left(e,𝒙\right)$.

We denote the weight function of each edge $e$ as follows:

and the conditional probability $p_{\lambda }\left(𝒚\right|𝒙)$ has the following form:

One of the most common model training methods for supervised dependency parser is Maximum conditional likelihood estimation. For a supervised dependency parser with a set of training data $\left\{\left({𝒙}_i,{𝒚}_i\right)\right\}$, the logarithm of the likelihood (a.k.a. the log-likelihood) is given by:

Maximum likelihood training chooses parameters such that the log-likelihood $L\left(\lambda \right)$ is maximized.

However, in our scenario we have no labeled training data for target languages but we have some parallel and unlabeled data plus an English dependency parser. For the purpose of transferring cross-lingual information from the English parser via parallel text, we explore the model training method proposed by Smith and Eisner [44], which presented a generalization of $K$ function [1], and related it to another semi-supervised learning technique, entropy regularization [20, 28]. The objective $K$ function to be minimized is actually the expected negative log-likelihood:

where ${\tilde{p}}_i(\cdot )\stackrel{def}{=}\tilde{p}(\cdot |{𝒙}_i)$ and $p_{\lambda ,i}(\cdot )\stackrel{def}{=}{p}_{\lambda }(\cdot |{𝒙}_i)$. $\tilde{p}\left(𝒚\right|𝒙)$ is the “transferring distribution” that reflects our uncertainty about the true labels, and we are trying to learn a parametric model $p_{\lambda }\left(𝒚\right|𝒙)$ by minimizing the $K$ function.

In our scenario, we have a set of aligned parallel data $P=\left\{{𝒙}_i^s,{𝒙}_i^t,a_i\right\}$ where $a_i$ is the word alignment for the pair of source-target sentences $\left({𝒙}_i^s,{𝒙}_i^t\right)$, and a set of unlabeled sentences of the target language $U=\left\{{𝒙}_i^t\right\}$. We also have a trained English parsing model $p_{{\lambda }_E}\left(𝒚\right|𝒙)$. Then the $K$ in equation (7) can be divided into two cases, according to whether ${𝒙}_i$ belongs to parallel data set $P$ or unlabeled data set $U$. For the unlabeled examples $\left\{{𝒙}_i\in U\right\}$, some previous studies (e.g., [1]) simply use a uniform distribution over labels (e.g., parses), to reflect that the label is unknown. We follow the method in Smith and Eisner [44] and take the transferring distribution ${\tilde{p}}_i$ to be the actual current belief $p_{\lambda ,i}$. The total contribution of the unsupervised examples to $K$ then simplifies to $K_U=\sum _{{𝒙}_i\in U}H\left(p_{\lambda ,i}\right)$, which may be regarded as the entropy item used to constrain the model’s uncertainty $H$ to be low, as presented in the work on entropy regularization [20, 28].

But how can we define the transferring distribution for the parallel examples $\left\{{𝒙}_i^t\in P\right\}$? We define the transferring distribution by defining the transferring weight utilizing the English parsing model $p_{{\lambda }_E}\left(𝒚\right|𝒙)$ via parallel data with word alignments:

where $w_E(\cdot ,\cdot )$ is the weight function of the English parsing model $p_{{\lambda }_E}\left(𝒚\right|𝒙)$, and $e_{delex}^t$ is the delexicalized form²²The delexicalized form of an edge is an edge for which only delexicalized features are considered. of the edge $e^t$. From the definition of the transferring weight, we can see that, if an edge $e^t$ of the target language sentence ${𝒙}_i^t$ is aligned to an edge $e^s$ of the English sentence ${𝒙}_i^s$, we transfer the weight of edge $e^t$ to the corresponding weight of edge $e^s$ in the English parsing model $p_{{\lambda }_E}\left(𝒚\right|𝒙)$. If the edge $e^t$ is not aligned to any edges of the English sentence ${𝒙}_i^s$, we reduce the edge $e^t$ to the delexicalized form and calculate the transferring weight in the English parsing model. There are two advantages for this definition of the transferring weight. First, by transferring the weight function to the corresponding weight in the well-developed English parsing model, we can project syntactic information across language boundaries. Second, McDonald et al. [34] demonstrates that parsers with only delexicalized features produce considerably high parsing performance. By reducing unaligned edges to their delexicalized forms, we can still use those delexicalized features, such as part-of-speech tags, for those unaligned edges, and can address problem that automatically generated word alignments include errors.

From the definition of transferring weight in equation (8), the transferring distribution can be defined in the following way:

where

Due to the normalizing factor $\tilde{Z}\left(𝒙\right)$, the transferring distribution is a valid one.

We introduce a multiplier $\gamma$ as a trade-off between the two contributions (parallel and unsupervised) of the objective function $K$, and the final objective function $K^{{}^{\prime }}$ has the following form:

$K_P$ and $K_U$ are the contributions of the parallel and unsupervised data, respectively. One may regard $\gamma$ as a Lagrange multiplier that is used to constrain the parser’s uncertainty H to be low, as presented in several studies on entropy regularization [5, 17, 20].

To train our parsing model, we need to find out the parameters $\lambda$ that minimize the objective function $K^{{}^{\prime }}$ in equation (11). This optimization problem is typically solved using quasi-Newton numerical methods such as L-BFGS [36], which requires efficient calculation of the objective function and the gradient of the objective function.

The first item ($K_P$) of the $K^{{}^{\prime }}$ function in equation (11) can be rewritten in the following form:

and according to equation (1) and (3) the gradient of $K_P$ can be written as:

According to equation (9), $\tilde{p}\left(𝒚\right|𝒙)$ can also be factored into the multiplication of the weight of each edge, so both $K_P$ and its gradient can be calculated by running the $O\left(n^3\right)$ inside-outside algorithm [2, 41] for projective parsing. For non-projective parsing, the analogy to the inside algorithm is the $O\left(n^3\right)$ matrix-tree algorithm based on Kirchhoff’s Matrix-Tree Theorem, which is dominated asymptotically by a matrix determinant [25, 46]. The gradient of a determinant may be computed by matrix inversion, so evaluating the gradient again has the same $O\left(n^3\right)$ complexity as evaluating the function.

The second item ($K_U$) of the $K^{{}^{\prime }}$ function in equation (11) is the Shannon entropy of the posterior distribution over parsing trees, and can be written into the following form:

and the gradient of $K_U$ is in the following:

Similar with the calculation of $K_P$, $K_U$ can also be computed by running the inside-outside algorithm [2, 41] for projective parsing. For the gradient of $K_U$, both the two multipliers of the second item in equation (15) can be computed using the same inside-outside algorithm. For the first item in equation (15), an $O\left(n^3\right)$ dynamic programming algorithm that is closely related to the forward-backward algorithm [28] for the entropy regularized CRF [20] can be used for projective parsing. For non-projective parsing, however, the runtime rises to $O\left(n^4\right)$. In this paper, we focus on projective parsing.

To summarize the description in the previous sections, our approach is performed in the following steps:

1. 1.

   Train an English parsing model $p_{{\lambda }_E}\left(𝒚\right|𝒙)$, which is used to estimate the transferring distribution $\tilde{p}\left(𝒚\right|𝒙)$.

2. 2.

   Prepare parallel text by running word alignment method to obtain word alignments,³³The word alignment methods do not require additional resources besides parallel text. and prepare the unlabeled data.

3. 3.

   Train a parsing model for the target language by minimizing the objective $K^{{}^{\prime }}$ function which is the combination of expected negative log-likelihood on parallel and unlabeled data.

Our experiments rely on two kinds of data sets: (i) Monolingual Treebanks with consistent annotation schema — English treebank is used to train the English parsing model, and the Treebanks for target languages are used to evaluate the parsing performance of our approach. (ii) Large amounts of parallel text with English on one side. We select target languages based on the availability of these resources. The monolingual treebanks in our experiments are from the Google Universal Dependency Treebanks [31], for the reason that the treebanks of different languages in Google Universal Dependency Treebanks have consistent syntactic representations.

The parallel data come from the Europarl corpus version 7 [23] and Kaist Corpus⁴⁴http://semanticweb.kaist.ac.kr/home/index.php/Corpus10. Taking the intersection of languages in the two kinds of resources yields the following seven languages: French, German, Italian, Korean, Portuguese, Spanish and Swedish.

The treebanks from CoNLL shared-tasks on dependency parsing [6, 38] appear to be another reasonable choice. However, previous studies [34, 31] have demonstrated that a homogeneous representation is critical for multilingual language technologies that require consistent cross-lingual analysis for downstream components, and the heterogenous representations used in CoNLL shared-tasks treebanks weaken any conclusion that can be drawn.

For comparison with previous studies, nevertheless, we also run experiments on CoNLL treebanks (see Section 4.4 for more details). We evaluate our approach on three target languages from CoNLL shared task treebanks, which do not appear in Google Universal Treebanks. The three languages are Danish, Dutch and Greek. So totally we have ten target languages. The parallel data for these three languages are also from the Europarl corpus version 7.

In our approach, word alignments for the parallel text are required. We perform word alignments with the open source GIZA++ toolkit⁵⁵https://code.google.com/p/giza-pp/. The parallel corpus was preprocessed in standard ways, selecting sentences with the length in the range from 3 to 100. Then we run GIZA++ with the default setting to generate word alignments in both directions. We then make the intersection of the word alignments of two directions to generate one-to-one alignments.

Several features in our parsing model involve part-of-speech (POS) tags of the input sentences. The set of POS tags needs to be consistent across languages and treebanks. For this reason we use the universal POS tag set of Petrov et al. [42]. This set consists of the following 12 coarse-grained tags: NOUN (nouns), VERB (verbs), ADJ (adjectives), ADV (adverbs), PRON (pronouns), DET (determiners), ADP (prepositions or postpositions), NUM (numerals), CONJ (conjunctions), PRT (particles), PUNC (punctuation marks) and X (a catch-all for other categories such as abbreviations or foreign words).

POS tags are not available for parallel data in the Europarl and Kaist corpus, so we need to provide the POS tags for these data. In our experiments, we train a Stanford POS Tagger [50] for each language. The labeled training data for each POS tagger are extracted from the training portion of each Treebanks. The average tagging accuracy is around 95%.

Undoubtedly, we are primarily interested in applying our approach to build statistical parsers for resource-poor target languages without any knowledge. For the purpose of evaluation of our approach and comparison with previous work, we need to exploit the gold POS tags to train the POS taggers. As part-of-speech tags are also a form of syntactic analysis, this assumption weakens the applicability of our approach. Fortunately, some recently proposed POS taggers, such as the POS tagger of Das and Petrov [13], rely only on labeled training data for English and the same kind of parallel text in our approach. In practice we can use this kind of POS taggers to predict POS tags, whose tagging accuracy is around 85%.

As presented in Section 3.1, we evaluate our parsing approach on both version 1.0 and version 2.0 of Google Univereal Treebanks for seven languages⁶⁶Japanese and Indonesia are excluded as no practicable parallel data are available.. We use the standard splits of the treebank for each language as specified in the release of the data⁷⁷https://code.google.com/p/uni-dep-tb/. Table 1 presents the statistics of the two versions of Google Universal Treebanks. We strip all the dependency annotations off the training portion of each treebank, and use that as the unlabeled data for that target language. We train our parsing model with different numbers of parallel sentences to analyze the influence of the amount of parallel data on the parsing performance of our approach. The parallel data sets contain 500, 1000, 2000, 5000, 10000 and 20000 parallel sentences, respectively. We randomly extract parallel sentences from each corpora, and smaller data sets are subsets of larger ones. Table 2 shows the number of tokens in the parallel data used in the experiments.

For the comparison of parsing performance, we run experiments on the following systems:

DTP:

The direct transfer parser (DTP) proposed by McDonald et al. [34], who train a delexicalized parser on English labeled training data with no lexical features, then apply this parser to parse target languages directly. It is based on the transition-based dependency parsing paradigm [40]. We directly cite the results reported in McDonald et al. [31]. In addition to their original results, we also report results by re-implementing the direct transfer parser based on the first-order projective dependency parsing model [30] (DTP†).

PTP

The projected transfer parser (PTP) described in McDonald et al. [34]. The results of the projected transfer parser re-implemented by us is marked as “PTP†”.

-U:

Our approach training on only parallel data without unlabeled data for the target language. The parallel data set for each language contains 20,000 sentences.

+U:

Our approach training on both parallel and unlabeled data. The parallel data sets are the ones contains 20,000 sentences.

OR:

the supervised first-order projective dependency parsing model [30], trained on the original treebanks with maximum likelihood estimation (equation 6). One may regard this system as an oracle of transfer parsing.

Parsing accuracy is measured with unlabeled attachment score (UAS): the percentage of words with the correct head.

Table 3 and Table 4 shows the parsing results of our approach, together with the results of the baseline systems and the oracle, on version 1.0 and version 2.0 of Google Universal Treebanks, respectively. Our approaches significantly outperform all the baseline systems across all the seven target languages. For the results on Google Universal Treebanks version 1.0, the improvement on average over the projected transfer paper (PTP†) is 3.96% and up to 6.22% for Korean and 4.80% for German. For the other three languages, the improvements are remarkable, too — 2.33% for French, 3.03% for Spanish and 3.40% for Swedish. By adding entropy regularization from unlabeled data, our full model achieves average improvement of 0.29% over the “-U” setting. Moreover, our approach considerably bridges the gap to fully supervised dependency parsers, whose average UAS is 84.67%. For the results on treebanks version 2.0, we can get similar observation and draw the same conclusion.

Table 5 illustrates the UAS of our approach trained on different amounts of parallel data, together with the results of the projected transfer parser re-implemented by us (PTP†). We run two versions of our approach for each of the parallel data sets, one with unlabeled data (+U) and the other without them (-U). From table 5 we can get three observations. First, even the parsers trained with only 500 parallel sentences achieve considerably high parsing accuracies (average 70.10% for version 1.0 and 71.59% for version 2.0). This demonstrates that our approach does not rely on a large amount of parallel data. Second, when gradually increasing the amount of parallel data, the parsing performance continues improving. Third, entropy regularization with unlabeled data makes modest improvement on parsing performance over the parsers without unlabeled data. This proves the effectiveness of the entropy regularization from unlabeled data.

To make a thorough empirical comparison with previous studies, we also evaluate our system without unlabeled data (-U) on treebanks from CoNLL shared task on dependency parsing [6, 38]. To facilitate comparison, we use the same eight Indo-European languages as target languages: Danish, Dutch, German, Greek, Italian, Portuguese, Spanish and Swedish, and same experimental setup as McDonald et al. [34]. We report both the results of the direct transfer and projected transfer parsers directly cited from McDonald et al. [34] (DTP and PTP) and re-implemented by us (DTP†and PTP†).

Table 6 gives the results comparing the model without unlabeled data (-U) presented in this work to those five baseline systems and the oracle (OR). The results of unsupervised DMV model [22] are from Table 1 of McDonald et al. [34]. Our approach outperforms all these baseline systems and achieves state-of-the-art performance on all the eight languages.

In order to compare with more previous methods, we also report parsing performance on sentences of length 10 or less after punctuation has been removed. Table 7 shows the results of our system and the results of baseline systems. “USR†” is the weakly supervised system of Naseem et al. [35]. “PGI” is the phylogenetic grammar induction model of Berg-Kirkpatrick and Klein [3]. Both the results of the two systems are cited from Table 4 of McDonald et al. [34]. We also include the results of the unsupervised dependency parsing model with non-parallel multilingual guidance (NMG) proposed by Cohen et al. [11]⁸⁸For each language, we use the best result of the four systems in Table 3 of Cohen et al. [11], and “PR” which is the posterior regularization approach presented in Gillenwater et al. [15]. All the results are shown in Table 7.

From Table 7, we can see that among the eight target languages, our approach achieves best parsing performance on six languages — Danish, German, Greek, Italian, Portuguese and Swedish. It should be noted that the “NMG” system utilizes more than one helper languages. So it is not directly comparable to our work.

In this section, we briefly outline a few extensions to our approach that we want to explore in future work.