A Recursive Recurrent Neural Network
for Statistical Machine Translation

Recurrent neural network is usually used for sequence processing, such as language model [12]. Commonly used sequence processing methods, such as Hidden Markov Model (HMM) and n-gram language model, only use a limited history for the prediction. In HMM, the previous state is used as the history, and for n-gram language model (for example  $n$  equals to 3), the history is the previous two words. Recurrent neural network is proposed to use unbounded history information, and it has recurrent connections on hidden states, so that history information can be used circularly inside the network for arbitrarily long time.

As shown in Figure 1, the network contains three layers, an input layer, a hidden layer, and an output layer. The input layer is a concatenation of  $h_{t-1}$  and $x_t$, where  $h_{t-1}$  is a real-valued vector, which is the history information from time 0 to  $t-1$. $x_t$ is the embedding of the input word at time  $t$ . Word embedding  $x_t$  is integrated with previous history  $h_{t-1}$  to generate the current hidden layer, which is a new history vector  $h_t$ . Based on  $h_t$ , we can predict the probability of the next word, which forms the output layer  $y_t$ . The new history  $h_t$  is used for the future prediction, and updated with new information from word embedding  $x_t$  recurrently.

In addition to the sequential structure above, tree structure is also usually constructed in various NLP tasks, such as parsing and SMT decoding. To generate a tree structure, recursive neural networks are introduced for natural language parsing [16]. Similar with recurrent neural networks, recursive neural networks can also use unbounded history information from the sub-tree rooted at the current node. The commonly used binary recursive neural networks generate the representation of the parent node, with the representations of two child nodes as the input.

As shown in Figure 2,  $s^{\left[l,m\right]}$  and  $s^{\left[m,n\right]}$  are the representations of the child nodes, and they are concatenated into one vector to be the input of the network.  $s^{\left[l,n\right]}$  is the generated representation of the parent node.  $y_{\left[l,n\right]}$  is the confidence score of how plausible the parent node should be created. $l,m,n$  are the indexes of the string. For example, for nature language parsing,  $s^{\left[l,n\right]}$  is the representation of the parent node, which could be a  $NP$  or  $VP$  node, and it is also the representation of the whole sub-tree covering from  $l$  to  $n$ .

Word embedding  $x_t$  is integrated as new input information in recurrent neural networks for each prediction, but in recursive neural networks, no additional input information is used except the two representation vectors of the child nodes. However, some global information , which cannot be generated by the child representations, is crucial for SMT performance, such as language model score and distortion model score. So as to integrate such global information, and also keep the ability to generate tree structure, we combine the recurrent neural network and the recursive neural network to be a recursive recurrent neural network (R²NN).

As shown in Figure 3, based on the recursive network, we add three input vectors  $x^{\left[l,m\right]}$  for child node  $\left[l,m\right]$ ,  $x^{\left[m,n\right]}$  for child node  $\left[m,n\right]$ , and  $x^{\left[l,n\right]}$  for parent node  $\left[l,n\right]$ . We call them recurrent input vectors, since they are borrowed from recurrent neural networks. The two recurrent input vectors  $x^{\left[l,m\right]}$  and  $x^{\left[m,n\right]}$  are concatenated as the input of the network, with the original child node representations  $s^{\left[l,m\right]}$  and  $s^{\left[m,n\right]}$ . The recurrent input vector  $x^{\left[l,n\right]}$  is concatenated with parent node representation  $s^{\left[l,n\right]}$  to compute the confidence score  $y^{\left[l,n\right]}$ .

The input, hidden and output layers are calculated as follows:

where  $\bowtie$  is a concatenation operator in Equation 1 and Equation 3, and  $f$  is a non-linear function, here we use  $HTanh$  function, which is defined as:

Figure 4 illustrates the R²NN architecture for SMT decoding. For a source sentence “laizi faguo he eluosi de”, we first split it into phrases “laizi”, “faguo he eluosi” and “de”. We then check whether translation candidates can be found in the translation table for each span, together with the phrase pair embedding and recurrent input vector (global features). We call it the rule matching phase. For a translation candidate of the span node  $\left[l,m\right]$ , the black dots stand for the node representation  $s^{\left[l,m\right]}$ , while the grey dots for recurrent input vector  $x^{\left[l,m\right]}$ . Given  $s^{\left[l,m\right]}$  and  $x^{\left[l,m\right]}$  for matched translation candidates, conventional CKY decoding process is performed using R²NN. R²NN can combine the translation pairs of child nodes, and generate the translation candidates for parent nodes with their representations and plausible scores. Only the n-best translation candidates are kept for upper combination, according to their plausible scores.

We extract phrase pairs using the conventional method [13]. The commonly used features, such as translation score, language model score and distortion score, are used as the recurrent input vector  $x$ . During decoding, recurrent input vectors  $x$  for internal nodes are calculated accordingly. The difference between our model and the conventional log-linear model includes:

• •

  R²NN is not linear, while the conventional model is a linear combination.

• •

  Representations of phrase pairs are automatically learnt to optimize the translation performance, while features used in conventional model are hand-crafted.

• •

  History information of the derivation can be recorded in the representation of internal nodes, while conventional model cannot.

Liu et al. (2013) apply DNN to SMT decoding, but not in a recursive manner. A feature is learnt via a one-hidden-layer neural network, and the embedding of words in the phrase pairs are used as the input vector. Our model generates the representation of a translation pair based on its child nodes. Li et al. (2013) also generate the representation of phrase pairs in a recursive way. In their work, the representation is optimized to learn a distortion model using recursive neural network, only based on the representation of the child nodes. Our R²NN is used to model the end-to-end translation process, with recurrent global information added. We also explore phrase pair embedding method to model translation confidence directly, which is introduced in Section 5.

In the next two sections, we will answer the following questions: (a) how to train the model, and (b) how to generate the initial representations of translation pairs.

We adopt the Recursive Auto Encoding (RAE) [16] for our unsupervised pre-training. The main idea of auto encoding is to initialize the parameters of the neural network, by minimizing the information lost, which means, capturing as much information as possible in the hidden states from the input vector.

As shown in Figure 5, RAE contains two parts, an encoder with parameter  $W$ , and a decoder with parameter  $W^{\prime }$ . Given the representations of child nodes  $s_1$  and  $s_2$ , the encoder generates the representation of parent node  $s$ . With the parent node representation  $s$  as the input vector, the decoder reconstructs the representation of two child nodes  $s_1^{\prime }$  and  $s_2^{\prime }$ . The loss function is defined as following so as to minimize the information lost:

where  $\parallel \cdot \parallel$  is the Euclidean norm.

The training samples for RAE are phrase pairs  $\left\{s_1,s_2\right\}$  in translation table, where  $s_1$  and  $s_2$  can form a continuous partial sentence pair in the training data. When RAE training is done, only the encoding model  $W$  will be fine tuned in the future training phases.

We use contrastive divergence method to fine tune the parameters  $W$  and  $V$ . The loss function is the commonly used ranking loss with a margin, and it is defined as follows:

where  $s^{\left[l,n\right]}$  is the source span.  $y_{oracle}^{\left[l,n\right]}$  is the plausible score of a oracle translation result.  $y_t^{\left[l,n\right]}$  is the plausible score for the best translation candidate given the model parameters  $W$  and  $V$ . The loss function aims to learn a model which assigns the good translation candidate (the oracle candidate) higher score than the bad ones, with a margin 1.

Translation candidates generated by forced decoding [18] are used as oracle translations, which are the positive samples. Forced decoding performs sentence pair segmentation using the same translation system as decoding. For each sentence pair in the training data, SMT decoder is applied to the source side, and any candidate which is not the partial sub-string of the target sentence is removed from the n-best list during decoding. From the forced decoding result, we can get the ideal derivation tree in the decoder’s search space, and extract positive/oracle translation candidates.

The supervised local training uses the nodes/samples in the derivation tree of forced decoding to update the model, and the trained model tends to over-fit to local decisions. In this subsection, a supervised global training is proposed to tune the model according to the final translation performance of the whole source sentence.

Actually, we can update the model from the root of the decoding tree and perform back propagation along the tree structure. Due to the inexact search nature of SMT decoding, search errors may inevitably break theoretical properties, and the final translation results may be not suitable for model training. To handle this problem, we use early update strategy for the supervised global training. Early update is testified to be useful for SMT training with large scale features [21]. Instead of updating the model using the final translation results, early update approach optimizes the model, when the oracle translation candidate is pruned from the n-best list, meaning that, the model is updated once it performs a unrecoverable mistake. Back propagation is performed along the tree structure, and the phrase pair embeddings of the leaf nodess are updated.

The loss function for supervised global training is defined as follows:

where  $y_{oracle}^{\left[l,n\right]}$  is the model score of a oracle translation candidate for the span  $\left[l,n\right]$ . Oracle translation candidates are candidates get from forced decoding. If the span  $\left[l,n\right]$  is not the whole source sentence, there may be several oracle translation candidates, otherwise, there is only one, which is exactly the target sentence. There are much fewer training samples than those for supervised local training, and it is not suitable to use ranking loss for global training any longer. We use negative log-likelihood to penalize all the other translation candidates except the oracle ones, so as to leverage all the translation candidates as training samples.

Large scale feature training has drawn more attentions these years [10, 21]. Instead of integrating the sparse features directly into the log-linear model, we use them as the input to learn a phrase pair embedding. For the top 200,000 frequent translation pairs, each of them is a feature in itself, and a special feature is added for all the infrequent ones.

The one-hot representation vector is used as the input, and a one-hidden-layer network generates a confidence score. To train the neural network, we add the confidence scores to the conventional log-linear model as features. Forced decoding is utilized to get positive samples, and contrastive divergence is used for model training. The neural network is used to reduce the space dimension of sparse features, and the hidden layer of the network is used as the phrase pair embedding. The length of the hidden layer is empirically set to 20.

We use recurrent neural network to generate two smoothed translation confidence scores based on source and target word embeddings. One is source to target translation confidence score and the other is target to source. These two confidence scores are defined as:

where,  $f_{a_i}$  is the corresponding target word aligned to  $e_i$ , and it is similar for  $e_{{\widehat{a}}_j}$ .  $p\left(e_i\right|e_{i-1},f_{a_i},h_i)$  is produced by a recurrent network as shown in Figure 6. The recurrent neural network is trained with word aligned bilingual corpus, similar as [1].

The data is from the IWSLT 2009 dialog task. The training data includes the BTEC and SLDB training data. The training data contains 81k sentence pairs, 655K Chinese words and 806K English words. The language model is a 5-gram language model trained with the target sentences in the training data. The test set is development set 9, and the development set comprises both development set 8 and the Chinese DIALOG set.

The training data for monolingual word embedding is Giga-Word corpus version 3 for both Chinese and English. Chinese training corpus contains 32M sentences and 1.1G words. English training data contains 8M sentences and 247M terms. We only train the embedding for the top 100,000 frequent words following [3]. With the trained monolingual word embedding, we follow [20] to get the bilingual word embedding using the IWSLT bilingual training data.

Our baseline decoder is an in-house implementation of Bracketing Transduction Grammar (BTG) [17] in CKY-style decoding with a lexical reordering model trained with maximum entropy [19]. The features of the baseline are commonly used features as standard BTG decoder, such as translation probabilities, lexical weights, language model, word penalty and distortion probabilities. All these commonly used features are used as recurrent input vector  $x$  in our R²NN.

As we mentioned in Section 5, constructing phrase pair embeddings from word embeddings may be not suitable. Here we conduct experiments to verify it. We first train the source and target word embeddings separately using large monolingual data, following [3]. Using monolingual word embedding as the initialization, we fine tune them to get bilingual word embedding [20].

The word embedding based phrase pair embedding (WEPPE) is defined as:

where  $\bowtie$  is a concatenation operator.  $s$  and  $t$  are the source and target phrases.  $E_{wms}\left(s_i\right)$  and  $E_{wmt}\left(t_k\right)$  are the monolingual word embeddings, and  $E_{wbs}\left(s_i\right)$  and  $E_{wbt}\left(t_k\right)$  are the bilingual word embeddings. Here the length of the word embedding is also set to 20. Therefore, the length of the phrase pair embedding is  $20\times 4=80$ .

We compare our phrase pair embedding methods and our proposed R²NN with baseline system, in Table 2. We can see that, our R²NN models with WEPPE and TCBPPE are both better than the baseline system. WEPPE cannot get significant improvement, while TCBPPE does, compared with the baseline result. TCBPPE is much better than WEPPE.

Word embedding can model translation relationship at word level, but it may not be powerful to model the phrase pair respondents at phrasal level, since the meaning of some phrases cannot be decomposed into the meaning of words. And also, translation task is difference from other NLP tasks, that, it is more important to model the translation confidence directly (the confidence of one target phrase as a translation of the source phrase), and our TCBPPE is designed for such purpose.

In order to compare R²NN with recursive network for SMT decoding, we remove the recurrent input vector in R²NN to test its effect, and the results are shown in Table 3. Without the recurrent input vectors, R²NN degenerates into recursive neural network (RNN).

From Table 3 we can find that, the recurrent input vector is essential to SMT performance. When we remove it from R²NN, WEPPE based method drops about 10 BLEU points on development data and more than 6 BLEU points on test data. TCBPPE based method drops about 3 BLEU points on both development and test data sets. When we remove the recurrent input vectors, the representations of recursive network are generated with the child nodes, and it does not integrate global information, such as language model and distortion model, which are crucial to the performance of SMT.

To test the contributions of sparse features and recurrent network features, we first remove all the recurrent network features to train and test our R²NN model, and then remove all the sparse features to test the contribution of recurrent network features.

The results are shown in Table 6.4. From the results, we can find that, sparse features are more effective than the recurrent network features a little bit. The sparse features can directly model the translation correspondence, and they may be more effective to rank the translation candidates, while recurrent neural network features are smoothed lexical translation confidence.