Recurrent Neural Networks for Word Alignment Model

Given a source language sentence $f_1^J=f_1,\mathrm{\dots },f_J$ and a target language sentence $e_1^I=e_1,\mathrm{\dots },e_I$, $f_1^J$ is generated by $e_1^I$ via the alignment $a_1^J=a_1,\mathrm{\dots },a_J$. Each $a_j$ is a hidden variable indicating that the source word $f_j$ is aligned to the target word $e_{a_j}$. Usually, a “null” word $e_0$ is added to the target language sentence and $a_1^J$ may contain $a_j=0$, which indicates that $f_j$ is not aligned to any target word. The probability of generating the sentence $f_1^J$ from $e_1^I$ is defined as

The IBM Models 1 and 2 and the HMM model decompose it into an alignment probability $p_a$ and a lexical translation probability $p_t$ as

The three models differ in their definition of alignment probability. For example, the HMM model uses an alignment probability with a first-order Markov property: $p_a\left(a_j\right|a_j-a_{j-1})$. In addition, the IBM models 3-5 are extensions of these, which consider the fertility and distortion of each translated word.

These models are trained using the expectation-maximization algorithm [8] from bilingual sentences without word-level alignments (unlabeled training data). Given a specific model, the best alignment (Viterbi alignment) of the sentence pair ($f_1^J$, $e_1^I$) can be found as

For example, the HMM model identifies the Viterbi alignment using the Viterbi algorithm.

As an instance of discriminative models, we describe an FFNN-based word alignment model [40], which is our baseline. An FFNN learns a hierarchy of nonlinear features that can automatically capture complex statistical patterns in input data. Recently, FFNNs have been applied successfully to several tasks, such as speech recognition [7], statistical machine translation [20, 38], and other popular natural language processing tasks [6, 5].

Yang et al. [40] have adapted a type of FFNN, i.e., CD-DNN-HMM [7], to the HMM alignment model. Specifically, the lexical translation and alignment probability in Eq. 2 are computed using FFNNs as

where $t_a$ and $t_{lex}$ are an alignment score and a lexical translation score, respectively, $s_{NN}$ is a score of alignments $a_1^J$, and “$c\left(\text{a word }w\right)$” denotes a context of word $w$. Note that the model uses nonprobabilistic scores rather than probabilities because normalization over all words is computationally expensive. The model finds the Viterbi alignment using the Viterbi algorithm, similar to the classic HMM model. Note that alignments in the FFNN-based model are also governed by first-order Markov dynamics because an alignment score depends on the previous alignment $a_{j-1}$.

Figure 1 shows the network structure with one hidden layer for computing a lexical translation probability $t_{lex}(f_j,e_{a_j}|c\left(f_j\right),c\left(e_{a_j}\right))$. The model consists of a lookup layer, a hidden layer, and an output layer, which have weight matrices. The model receives a source and target word with their contexts as inputs, which are words in a predefined window (the window size is three in Figure 1). First, the lookup layer converts each input word into its word embedding by looking up its corresponding column in the embedding matrix ($L$), and then concatenates them. Let $V_f$ (or $V_e$) be a set of source words (or target words) and $M$ be a predetermined embedding length. $L$ is a $M\times \left(\left|V_f\right|+\left|V_e\right|\right)$ matrix¹¹We add a special token $⟨unk⟩$ to handle unknown words and $⟨null⟩$ to handle null alignments to $V_f$ and $V_e$. Word embeddings are dense, low dimensional, and real-valued vectors that can capture syntactic and semantic properties of the words [2]. The concatenation ($z_0$) is then fed to the hidden layer to capture nonlinear relations. Finally, the output layer receives the output of the hidden layer ($z_1$) and computes a lexical translation score.

The computations in the hidden and output layer are as follows²²Consecutive $l$ hidden layers can be used: $z_l=f\left(H_l\times z_{l-1}+B_{H_l}\right)$. For simplicity, this paper describes the model with 1 hidden layer.:

where $H$, $B_H$, $O$, and $B_O$ are $\left|z_1\right|\times \left|z_0\right|$, $\left|z_1\right|\times 1$, $1\times \left|z_1\right|$, and $1\times 1$ matrices, respectively, and $f\left(x\right)$ is an activation function. Following Yang et al. [40], a “hard” version of the hyperbolic tangent, htanh$\left(x\right)$³³htanh$\left(x\right)=-1$ for , htanh$\left(x\right)=1$ for $x>1$, and htanh$\left(x\right)=x$ for others., is used as $f\left(x\right)$ in this study.

The alignment model based on an FFNN is formed in the same manner as the lexical translation model. Each model is optimized by minimizing the following ranking loss with a margin using stochastic gradient descent (SGD)⁴⁴In our experiments, we used a mini-batch SGD instead of a plain SGD., where gradients are computed by the back-propagation algorithm [31]:

where $\theta$ denotes the weights of layers in the model, $T$ is a set of training data, ${𝒂}^{\mathbf{+}}$ is the gold standard alignment, ${𝒂}^{\mathbf{-}}$ is the incorrect alignment with the highest score under $\theta$, and $s_{\theta }$ denotes the score defined by Eq. 4 as computed by the model under $\theta$.

Dyer et al. [9] presented an unsupervised alignment model based on contrastive estimation (CE) [32]. CE seeks to discriminate observed data from its neighborhood, which can be viewed as pseudo-negative samples. Dyer et al. [9] regarded all possible alignments of the bilingual sentences, which are given as training data ($T$), and those of the full translation search space ($\mathrm{\Omega }$) as the observed data and its neighborhood, respectively.

We introduce this idea to a ranking loss with margin as

where $\mathrm{\Phi }$ is a set of all possible alignments given $\left(𝒇,𝒆\right)$, E${}_{\mathrm{\Phi }}\left[s_{\theta }\right]$ is the expected value of the scores $s_{\theta }$ on $\mathrm{\Phi }$, ${𝒆}^{\mathbf{+}}$ denotes a target language sentence in the training data, and ${𝒆}^{\mathbf{-}}$ denotes a pseudo-target language sentence. The first expectation term is for the observed data, and the second is for the neighborhood.

However, the computation for $\mathrm{\Omega }$ is prohibitively expensive. To reduce computation, we employ NCE, which uses randomly sampled sentences from all target language sentences in $\mathrm{\Omega }$ as ${𝒆}^{\mathbf{-}}$, and calculate the expected values by a beam search with beam width $W$ to truncate alignments with low scores. In our experiments, we set $W$ to 100. In addition, the above criterion is converted to an online fashion as

where ${𝒆}^{\mathbf{+}}$ is a target language sentence aligned to ${𝒇}^{\mathbf{+}}$ in the training data, i.e., $\left({𝒇}^{\mathbf{+}},{𝒆}^{\mathbf{+}}\right)\in T$, ${𝒆}^{\mathbf{-}}$ is a randomly sampled pseudo-target language sentence with length $\left|{𝒆}^{\mathbf{+}}\right|$, and $N$ denotes the number of pseudo-target language sentences per source sentence ${𝒇}^{\mathbf{+}}$. Note that $\left|{𝒆}^{\mathbf{+}}\right|=\left|{𝒆}^{\mathbf{-}}\right|$. GEN is a subset of all possible word alignments $\mathrm{\Phi }$, which is generated by beam search.

In a simple implementation, each ${𝒆}^{\mathbf{-}}$ is generated by repeating a random sampling from a set of target words ($V_e$) $\left|{𝒆}^{\mathbf{+}}\right|$ times and lining them up sequentially. To employ more discriminative negative samples, our implementation samples each word of ${𝒆}^{\mathbf{-}}$ from a set of the target words that co-occur with $f_i\in {𝒇}^{\mathbf{+}}$ whose probability is above a threshold $C$ under the IBM Model 1 incorporating $l_0$ prior [37]. The IBM Model 1 with $l_0$ prior is convenient for reducing translation candidates because it generates more sparse alignments than the standard IBM Model 1.

Both of the FFNN-based and RNN-based models are based on the HMM alignment model, and they are therefore asymmetric, i.e., they can represent one-to-many relations from the target side. Asymmetric models are usually trained in each alignment direction. The model proposed by Yang et al. [40] is no exception. However, it has been demonstrated that encouraging directional models to agree improves alignment performance [22, 21, 14, 11].

Inspired by their work, we introduce an agreement constraint to our learning. The constraint concretely enforces agreement in word embeddings of both directions. The proposed method trains two directional models concurrently based on the following objective by incorporating a penalty term that expresses the difference between word embeddings:

where ${\theta }_{FE}$ (or ${\theta }_{EF}$) denotes the weights of layers in a source-to-target (or target-to-source) alignment model, ${\theta }_L$ denotes weights of a lookup layer, i.e., word embeddings, and $\alpha$ is a parameter that controls the strength of the agreement constraint. $\parallel \theta \parallel$ indicates the norm of $\theta$. 2-norm is used in our experiments. Equations 13 and 14 can be applied to both supervised and unsupervised approaches. Equations 7 and 12 are substituted into $loss\left(\theta \right)$ in supervised and unsupervised learning, respectively. The proposed constraint penalizes overfitting to a particular direction and enables two directional models to optimize across alignment directions globally.

Our unsupervised learning procedure is summarized in Algorithm 1. In Algorithm 1, line 2 randomly samples $D$ bilingual sentences ${\left({𝐟}^{+},{𝐞}^{+}\right)}^D$ from training data $T$. Lines 3-1 and 3-2 generate $N$ pseudo-negative samples for each ${𝐟}^{+}$ and ${𝐞}^{+}$ based on the translation candidates of ${𝐟}^{+}$ and ${𝐞}^{+}$ found by the IBM Model 1 with $l_0$ prior, $IBM1$ (Section 4.1). Lines 4-1 and 4-2 update the weights in each layer following a given objective (Sections 4.1 and 4.2). Note that ${\theta }_{FE}^t$ and ${\theta }_{EF}^t$ are concurrently updated in each iteration, and ${\theta }_{EF}^t$ (or ${\theta }_{FE}^t$) is employed to enforce agreement between word embeddings when updating ${\theta }_{FE}^t$ (or ${\theta }_{EF}^t$).

We evaluated the alignment performance of the proposed models with two tasks: Japanese-English word alignment with the Basic Travel Expression Corpus ($BTEC$) [35] and French-English word alignment with the Hansard dataset ($Hansards$) from the 2003 NAACL shared task [23]. In addition, we evaluated the end-to-end translation performance of three tasks: a Chinese-to-English translation task with the FBIS corpus ($FBIS$), the IWSLT 2007 Japanese-to-English translation task ($IWSLT$) [10], and the NTCIR-9 Japanese-to-English patent translation task ($NTCIR$) [13]⁶⁶We did not evaluate the translation performance on the Hansards data because the development data is very small and performance is unreliable..

Table 1 shows the sizes of our experimental datasets. Note that the development data was not used in the alignment tasks, i.e., $BTEC$ and $Hansards$, because the hyperparameters of the alignment models were set by preliminary small-scale experiments. The $BTEC$ data is the first 9,960 sentence pairs in the training data for $IWSLT$, which were annotated with word alignment [12]. We split these pairs into the first 9,000 for training data and the remaining 960 as test data. All the data in $BTEC$ is word-aligned, and the training data in $Hansards$ is unlabeled data. In $FBIS$, we used the NIST02 evaluation data as the development data, and the NIST03 and 04 evaluation data as test data ($NIST03$ and $NIST04$).

We evaluated the proposed RNN-based alignment models against two baselines: the IBM Model 4 and the FFNN-based model with one hidden layer. The IBM Model 4 was trained by previously presented model sequence schemes [28]: $1^5{H}^5{3}^5{4}^5$, i.e., five iterations of the IBM Model 1 followed by five iterations of the HMM Model, etc., which is the default setting for GIZA++ ($IBM4$). For the FFNN-based model, we set the word embedding length $M$ to 30, the number of units of a hidden layer $\left|z_1\right|$ to 100, and the window size of contexts to 5. Hence, $\left|z_0\right|$ is 300 ($30\times 5\times 2$). Following Yang et al. [40], the FFNN-based model was trained by the supervised approach described in Section 2.2 ($FFN{N}_s$).

For the RNN-based models, we set $M$ to 30 and the number of units of each recurrent hidden layer $\left|y_j\right|$ to 100. Thus, $\left|x_j\right|$ is 60 ($30\times 2$). The number of units of each layer of the FFNN-based and RNN-based models and $M$ were set through preliminary experiments. To demonstrate the effectiveness of the proposed learning methods, we evaluated four types of RNN-based models: $RN{N}_s$, $RN{N}_{s+c}$, $RN{N}_u$, and $RN{N}_{u+c}$, where “$s$/$u$” denotes a supervised/unsupervised model and “$+c$” indicates that the agreement constraint was used.

In training all the models except $IBM4$, the weights of each layer were initialized first. For the weights of a lookup layer $L$, we preliminarily trained word embeddings for the source and target language from each side of the training data. We then set the word embeddings to $L$ to avoid falling into local minima. Other weights were randomly initialized to $\left[-0.1,0.1\right]$. For the pretraining, we used the RNNLM Toolkit ⁷⁷http://www.fit.vutbr.cz/~imikolov/rnnlm/ [24] with the default options. We mapped all words that occurred less than five times to the special token $⟨unk⟩$. Next, each weight was optimized using the mini-batch SGD, where batch size $D$ was 100, learning rate was 0.01, and an $l_2$ regularization parameter was 0.1. The training stopped after 50 epochs. The other parameters were set as follows: $W$, $N$ and $C$ in the unsupervised learning were 100, 50, and 0.001, respectively, and $\alpha$ for the agreement constraint was 0.1.

In the translation tasks, we used the Moses phrase-based SMT systems [17]. All Japanese and Chinese sentences were segmented by ChaSen⁸⁸http://chasen-legacy.sourceforge.jp/ and the Stanford Chinese segmenter⁹⁹http://nlp.stanford.edu/software/segmenter.shtml, respectively. In the training, long sentences with over 40 words were filtered out. Using the SRILM Toolkits [33] with modified Kneser-Ney smoothing, we trained a 5-gram language model on the English side of each training data for $IWSLT$ and $NTCIR$, and a 5-gram language model on the Xinhua portion of the English Gigaword corpus for $FBIS$. The SMT weighting parameters were tuned by MERT [29] in the development data.

Table 2 shows the alignment performance by the F1-measure. Hereafter, $MODEL\left(R\right)$ and $MODEL\left(I\right)$ denote the $MODEL$ trained from gold standard alignments and word alignments found by the IBM Model 4, respectively. In $Hansards$, all models were trained from randomly sampled 100 K data¹⁰¹⁰Due to high computational cost, we did not use all the training data. Scaling up to larger datasets will be addressed in future work.. We evaluated the word alignments produced by first applying each model in both directions and then combining the alignments using the “grow-diag-final-and” heuristic [18]. The significance test on word alignment performance was performed by the sign test with a 5% significance level. “+” in Table 2 indicates that the comparisons are significant over corresponding baselines, $IBM4$ and $FFN{N}_s\left(R/I\right)$.

In Table 2, $RN{N}_{u+c}$, which includes all our proposals, i.e., the RNN-based model, the unsupervised learning, and the agreement constraint, achieves the best performance for both $BTEC$ and $Hansards$. The differences from the baselines are statistically significant.

Table 2 shows that $RN{N}_s\left(R/I\right)$ outperforms $FFN{N}_s\left(R/I\right)$, which is statistically significant in $BTEC$. These results demonstrate that capturing the long alignment history in the RNN-based model improves the alignment performance. We discuss the difference of the RNN-based model’s effectiveness between language pairs in Section 6.1. Table 2 also shows that $RN{N}_{s+c}\left(R/I\right)$ and $RN{N}_{u+c}$ achieve significantly better performance than $RN{N}_s\left(R/I\right)$ and $RN{N}_u$ in both tasks, respectively. This indicates that the proposed agreement constraint is effective in training better models in both the supervised and unsupervised approaches.

In $BTEC$, $RN{N}_u$ and $RN{N}_{u+c}$ significantly outperform $RN{N}_s\left(I\right)$ and $RN{N}_{s+c}\left(I\right)$, respectively. The performance of these models is comparable with $Hansards$. This indicates that our unsupervised learning benefits our models because the supervised models are adversely affected by errors in the automatically generated training data. This is especially true when the quality of training data, i.e., the performance of $IBM4$, is low.

Table 3 shows the translation performance by the case sensitive BLEU4 metric¹¹¹¹We used mteval-v13a.pl as the evaluation tool (http://www.itl.nist.gov/iad/mig/tests/mt/2009/). [30]. Table 3 presents the average BLEU of three different MERT runs. In $NTCIR$ and $FBIS$, each alignment model was trained from the randomly sampled 100 K data, and then a translation model was trained from all the training data that was word-aligned by the alignment model. In addition, for a detailed comparison, we evaluated the SMT system where the IBM Model 4 was trained from all the training data ($IBM{4}_{all}$). The significance test on translation performance was performed by the bootstrap method [19] with a 5% significance level. “*” in Table 3 indicates that the comparisons are significant over both baselines, i.e., $IBM4$ and $FFN{N}_s\left(I\right)$.

Table 3 also shows that better word alignment does not always result in better translation, which has been discussed previously [40]. However, $RN{N}_u$ and $RN{N}_{u+c}$ outperform $FFN{N}_s\left(I\right)$ and $IBM4$ in all tasks. These results indicate that our proposals contribute to improving translation performance¹²¹²We also confirmed the effectiveness of our models on the NIST05 and NTCIR-10 evaluation data.. In addition, Table 3 shows that these proposed models are comparable to $IBM{4}_{all}$ in $NTCIR$ and $FBIS$ even though the proposed models are trained from only a small part of the training data.

Figure 3 shows word alignment examples from $FFN{N}_s$ and $RN{N}_s$, where solid squares indicate the gold standard alignments. Figure 3 (a) shows that $RR{N}_s$ adequately identifies complicated alignments with long distances compared to $FFN{N}_s$ (e.g., jaggy alignments of “have you been learning” in Fig 3 (a)) because $RN{N}_s$ captures alignment paths based on long alignment history, which can be viewed as phrase-level alignments, while $FFN{N}_s$ employs only the last alignment.

In French-English word alignment, the most valuable clues are located locally because English and French have similar word orders and their alignment has more one-to-one mappings than Japanese-English word alignment (Figure 3). Figure 3 (b) shows that both $RR{N}_s$ and $FFN{N}_s$ work for such simpler alignments. Therefore, the RNN-based model has less effect on French-English word alignment than Japanese-English word alignment, as indicated in Table 2.

Table 4 shows the alignment performance on $BTEC$ with various training data sizes, i.e., training data for $IWSLT$ (40 K), training data for $BTEC$ (9 K), and the randomly sampled 1 K data from the $BTEC$ training data. Note that $RN{N}_{s+c}\left(R\right)$ cannot be trained from the 40 K data because the 40 K data does not have gold standard word alignments.

Table 4 demonstrates that the proposed RNN-based model outperforms $IBM4$ trained from the unlabeled 40 K data by employing either the 1 K labeled data or the 9 K unlabeled data, which is less than 25% of the training data for $IBM4$. Consequently, the SMT system using $RN{N}_{u+c}$ trained from a small part of training data can achieve comparable performance to that using $IBM4$ trained from all training data, which is shown in Table 3.

The proposed unsupervised learning and agreement constraints can be applied to any NN-based alignment model. Table 5 shows the alignment performance of the FFNN-based models trained by our supervised/unsupervised approaches (s/u) with and without our agreement constraints. In Table 5, “+c” denotes that the agreement constraint was used, and “+” indicates that the comparison with its corresponding baseline, i.e., $FFN{N}_s$(I/R), is significant in the sign test with a 5% significance level.

Table 5 shows that $FFN{N}_{s+c}$(R/I) and $FFN{N}_{u+c}$ achieve significantly better performance than $FFN{N}_s$(R/I) and $FFN{N}_u$, respectively, in both $BTEC$ and $Hansards$. In addition, $FFN{N}_u$ and $FFN{N}_{u+c}$ significantly outperform $FFN{N}_s$(I) and $FFN{N}_{s+c}$(I), respectively, in $BTEC$. The performance of these models is comparable in $Hansards$. These results indicate that the proposed unsupervised learning and agreement constraint benefit the FFNN-based model, similar to the RNN-based model.