Discriminative Reordering Model Adaptation via Structural Learning

1 Introduction

Reordering model, as one of essential components of statistical machine translation (SMT), has become an active area of research in recent years [Zens and Ney, 2006; Xiong et al., 2006; Galley and Manning, 2008; Feng et al., 2013; Li et al., 2013; Alrajeh and Niranjan, 2014]. Particularly, discriminative reordering model (DRM) has attracted wide attention due to its advantage of easy fusion of various reordering features. However, similar to other discriminative models, a DRM trained on out-of-domain (e.g. newswire) corpus often performs badly on in-domain (e.g. weblog) data. This is because reordering patterns of translation units differs dramatically from one domain to another [Chen et al., 2013]. Therefore, building an adaptive DRM is crucial for SMT systems in practice.

A great variety of approaches have been proposed for language and translation model adaptation [Ueffing et al., 2007; Koehn and Schroeder, 2007; Bertoldi and Federico, 2009; Matsoukas et al., 2009; Foster et al., 2010; Axelrod et al., 2011; Phillips and Brown, 2011; Su et al., 2012; Sennrich, 2012; Duh et al., 2013; Cui et al., 2013; Chen et al., 2013; Hoang and Sima'an, 2014]. However, study on reordering model adaptation is very limited. In this respect, Chen et al. [2013] employed a linear mixture model that is trained on multiple parallel training corpus. Although the model achieves a significant improvement, they mainly focus on the exploitation of parallel corpora, of which many language pairs are short. They do not utilize monolingual corpora that are easier to be accessible.

∗Corresponding author.

Although reordering patterns and features differ in different domains, some of them are shared across domains. As illustrated in Figure 1, reordering features in domain weblog (e.g. net friends) differ extremely from those in domain newswire (e.g. water shortage). If we train a reordering model with the latter features, the performance in the former feature space is expected to be poor, since many features are not observed. Despite of this domain gap, the feature "one of " on the target side is a strong indicator for inverted orientation in both domains. To some extent, these domainindependent features can bridge the gap between different domains, from which a shared reordering sub-space can be induced, as shown by "Common Space" in Figure 1. Exploiting these domain-independent features (which we call pivot features following previous work) will, no doubt, be beneficial for reordering model adaptation.

In this paper, we propose a novel adaptive DRM for phrasebased SMT based on structural learning [Ando and Zhang, 2005; Blitzer et al., 2006]. Different from previous work, we directly exploit correlations of reordering features from indomain and out-of-domain monolingual corpora, and further learn a common feature representation for phrase reordering. Incorporating features of this common representation, the DRM trained on out-of-domain corpus is able to generalize better to in-domain data. Particularly,

• First, we select domain-shared pivot features according to two criteria: 1) frequency in monolingual corpora of different domains, and 2) information gain ratio in outof-domain parallel corpus;
• Second, we construct reordering-related auxiliary problems with pivot features, and learn a transformation matrix to common space from monolingual corpora using structural learning;
• Finally, we train a new reordering model on out-ofdomain bilingual corpora with the combination of original and transformed features.

We incorporate the adaptive reordering model into SMT and conduct experiments on the NIST Chinese-English translation task to evaluate its effectiveness. Results on the NIST 08 web part show that our model achieves a significant improvement over the baseline methods. The main contributions of our work are in two folds:

• We employ structural learning (Section 3.2) to DRM, and propose reordering-specific pivot feature selection (Section 3.1) and predictor construction (Section 3.1) methods using large-scale monolingual domain data. The utilization of structural learning to DRM, to the best of our knowledge, has never been investigated before.
• We conduct a series of experiments to demonstrate the effectiveness of our model and investigate the influence of various factors on translation quality (See Section 4).

2 MaximumEntropy Based Reordering Model

Many researchers have introduced different DRMs for phrase reordering [Xiong et al., 2006; He et al., 2010; Huck et al., 2012; Alrajeh and Niranjan, 2014]. Without loss of generality, here we focus on the maximum entropy based reordering model (MERM) proposed by Xiong et al. [2006].

Generally, MERM considers phrase reordering as a classification problem, under bracketing transduction grammar (BTG) [Wu, 1997]. There are three types of rules in BTG:

where reordering rules (1) and (2) are used to merge two neighboring blocks in a straight or inverted order, respectively. Lexical rule (3) is used to translate a source phrase f into a target phrase e. Correspondingly, there are only two labels, o ∈ {straight, inverted}, in MERM.

Different from relative-frequency based approaches which bind reorderings to individual concrete phrases, MERM is able to integrate arbitrary and overlapping features extracted from data. The probability that two neighboring blocks A1 and A2 are combined in the orientation o is computed as follows:

where hi ∈ {0, 1} are the feature functions and θi are weights of the model features. In our paper, we investigate three kinds of features, all of which are located at the boundaries of A1 and A2 following Xiong et al. [2006]. Specifically, for each block, we define the following features:

• N-gram: unigrams and bigrams on the left and right boundary of a block 1 .
• Word Class: word classes of unigrams.
• PoS: part of speech tags of unigrams (source side only) Consider the phrase "my old net friends" in Figure 1. Ngram features are given here: A2 .Left.my, A2 .Left.my old, A2 .Right.friends, A2 .Right.net friends, where Left and Right indicate the left-side and right-side boundary, respectively.

Despite the ability of incorporating arbitrary features, this model often performs badly on the test data that are different from training data in terms of their domains. We will discuss how to address this issue with structural learning in the next section.

3 Our Model

Given an out-of-domain parallel corpus consisting of monolingual corpora from the source language Dout m,f and the target language Dout m,e , and in-domain monolingual corpora for the source language Din m,f and the target language Din m,e , we aim at learning a common feature representation that is meaningful across different domains using only unlabeled data from both in-domain and out-of-domain corpora. The key idea is to leverage monolingual corpora to generate auxiliary problems for each language that are useful for discovering important correspondences among reordering features from different domains. Intuitively, if these created auxiliary problems are similar or at least related to the reordering problem, we will benefit from solving them.

Let us revisit the example shown in Figure 1. The reordering instance in red dash box comes from newswire and blue dash box weblog. Although the context vary greatly, the target-side bigram "one of " strongly indicates that the neighbor blocks are in inverted order in whichever domain. Intuitively, these features connect domain-specific features. Therefore we would like to learn these domain-independent features. It is worth noting that these features can be learned from unlabeled monolingual data, thus breaking down the bilingual corpus barrier.

We first elaborate auxiliary problem in Section 3.1. Then, we detail structural learning in Section 3.2, and present how we learn an adaptive DRM via structural learning.

Due to the space limit, we only describe the learning procedure for the target language (English), omitting the procedure for the source language (Chinese), which can be implemented in a similar way.

3.1 Auxiliary Classification Problems

Pivot Feature Selection

Pivot features are features that occur frequently and behave similarly in corpora of different domains [Blitzer et al., 2006].

1 A unigram refers to a word and a bigram refers to two adjacent words.

The selection of pivot features is a crucial step in structural learning, since they are used to establish the correlation between two different domains. Similar to Blitzer et al. [2006] and Prettenhofer and Stein [2010], we select pivot features according to the following two criteria:

• Pivot features should occur frequently in both in-domain and out-of-domain corpora;
• Pivot features should be useful for reordering prediction.

Although pivot features can be n-grams, word classes or PoS tags, we only focus on n-gram features in this paper. In order to meet the first criterion, we extract frequent unigrams and bigrams from Din m,e and Dout m,e with a frequency threshold ϵ1, and annotate them with corresponding positions (A2 .Right, A2 .Left, A1 .Right, A1 .Left). These annotated ngram features are used as our candidate pivot features. They ensure that correlations between different domains can be estimated accurately. With regard to the second criterion, we calculate information gain ratio (IGR) for candidate features that satisfy the first criterion on reordering examples extracted from the out-of-domain parallel corpus and select top m candidates as final pivot features according to their IGR values. This way can ensure that only those correlations that are useful for discriminative learning will be modeled.

Each pivot feature for reordering consists of an n-gram (e.g. one of ) and a position (e.g. A1 .Right). We give some top pivot features selected in our model in Table 1. Most of them, as expected, are function words that often encode grammatical relations among phrases within a sentence and greatly affect phrase reordering. For example, the target-side feature "one of " with position A1 .Right in Figure 1 satisfies the two characteristics mentioned above: (1) it strongly indicates the inverted reordering orientation, and (2) it occurs frequently in both newswire and weblog domain. Thus, it is an ideal pivot feature for order predicting.

Pivot Feature Predictors

After obtaining pivot features, we conduct an auxiliary classification task on monolingual corpora Din m,e and Dout m,e . For each pivot feature fp, we construct a binary classifier to predict whether it occurs in a reordering instance. Since reordering instances in SMT are extracted from parallel corpus, a serious challenge here is to extract related pivot features as well as reordering-specific training examples from monolingual corpus.

To tackle this challenge, we adopt an imitation strategy to extract pseudo reordering instances from monolingual corpora according to their reordering behaviors. Basically, for a monolingual sentence, we try to select two neighboring phrases within a limited window size sl (left phrase) and sr A1 .Left: . . . this place has become ⟨one of the⟩⟨mainland 's⟩ . . .

Figure 2: Training instance extraction from example sentence "Today this place has become one of the mainland 's largest ocean-going container freight ports ." for pivot n-gram "one of ". Each instance corresponds to a pivot label, which is A2 .Right, A2 .Left, A1 .Right, A1 .Left from top to bottom. 〈·〉 represents a monolingual phrase, and we set sl = sr = 2 for better illustration.

(right phrase) to simulate the two adjacent blocks in reordering. If a sentence contains the n-gram in fp, we directly select neighboring phrases according to the n-gram (e.g. one of ) and position (e.g. A1 .Right) in fp, and treat this instance as a positive instance. An example is illustrated in Figure 2. Suppose that fp is "A1 .Right.one of ", we will choose the third instance as our positive one.

For a sentence S without the n-gram in fp, we construct a pseudo pivot feature f ′p with the position of fp and an n-gram chose from S. A negative instance is further extracted from S with f ′p . In regard to the n-gram, we first extract a frequent n-gram set S in and S out from Din m,e and Dout m,e respectively according to a threshold ϵ2. Afterwards we randomly pick an n-gram from A: the intersection of S and S in - S out for indomain sentence (or S and S out - S in for out-of-domain sentence). If A is empty, we choose the n-gram randomly from B: the intersection of S and S in ∩S out . If B is also empty, we simply select an n-gram randomly from S. Thus, the selected n-gram will be not only frequent, but also domain-specific, which ensures the accuracy of learned correlations.

Features for a pivot predictor are the same as those in MERM defined in Section 2, except for the pivot feature itself. In practice, negative and positive training examples are extremely imbalanced. To overcome this problem, we randomly select training instances to approximately make the ratio of negative to positive examples 2:1, as implemented in [Hernault et al., 2011].

3.2 Adaptive DRMBased on Structural Learning

Assume that we have a training set consisting of T reordering examples {ht, ot}Tt=1 , where ht is a reordering feature vector with dimension d and orientation ot; we also have a largescale unlabeled corpus {hj} collected from Dout m,e and Din m,e , where hj ∈ Rd is the feature vector extracted from monolingual sentence. Based on structural learning, we learn an adaptive DRM in the following steps.

In Step 1, we first choose m pivot features which have similar effects on phrase movements in different domains (Section 3.1), and then define a predictor for each pivot feature based on simple linear classifier (Section 3.1). For each predictor pl, l = 1 . . .m, we learn the optimal weight vector ˆwl in the following way

where L is a loss function and λ a regularization coefficient, and pl(hj) indicates the binary label for hj.

In Step 2, through the above-mentioned predictors, we induce a mapping θ from the original reordering feature spaces of both domains to a shared, low-dimensional real-valued feature space. In the specific implementation, we first create a matrix W = [ ˆw1 . . . ˆwm] in a column-per-column fashion, and then perform a singular value decomposition (SVD) on this matrix to reduce its dimension. In this way, we can learn a compact representation of the space of auxiliary classifiers.

Note that typically DRM employ several types of heterogeneous features, such as phrases, word classes and PoS tags. Hence we perform a localized dimension reduction for each type of feature. For each feature type fi, i ∈ [1 . . . n] with start position si and end position ei in the feature space, we create a feature-type-specific structural parameter matrix θi so that,

where Wi = UiDiV T i . Assume that the diagonal elements of Di are arranged in decreasing order. The rows of θi are given by the first k rows of U T i , which are the left singular vectors corresponding to the largest k singular values of Wi. Therefore, the complete structural parameter matrix θ = [θ1 . . . θn] has dimension k × d, and it encodes the structure learned by the auxiliary tasks in a low-dimensional common space.

In Step 3, both the original features h and transformed features θh are used simultaneously to construct the reordering classifier. We project each training and test feature vector of DRM onto θ, and obtain a set of k new structural features, which are then appended to their original feature vector. Formally, we extend the feature set in the following way:

In Step 4, we rescale extended features to unit length, θht ‖θht‖ .

Compared with DRM trained only with original features, the model trained on adjusted feature set would put much more emphasis on the transformed features. Because these features are shared across domains, our model will benefit more from them and generalize better when transferring to in-domain data. Note that in our model, we have two kinds of transformed features (from the source and target language respectively). We empirically concatenate them together with the original features h into a single feature vector, which is feed into the MERM for reordering.

4 Experiments

We conduct experiments on the NIST Chinese-to-English translation task to evaluate our model. After a brief description of the data preparation and the experimental setup, we first studied the effects of various factors on the reordering classification results, and then investigated the effectiveness of our method.

4.1 Data Preparation

The out-of-domain (newswire) training corpus comes from the FBIS corpus and Hansards part of LDC2004T07 corpus. We used the Chinese Sohu weblog in 2009 2 and the English Blog Authorship corpus 3 as the in-domain (weblog) monolingual corpora in the source language and target language, respectively. For these monolingual data, we first preprocessed them with Stanford NLP toolkit 4 , and then filtered noisy blog documents and those consisting of short sentences.

Because some important parameters such as the pivot feature number m and reduced dimension k directly influence the performance of our approach, we used the web part of NIST 06 MT evaluation test data as our development set to obtain the optimal parameters, and the web part of the 2008 NIST MT test data, as the final test set. The statistics of the various data sets are shown in Table 2.

4.2 Setup

We word-aligned the training corpus using GIZA++ 5 with the option "grow-diag-final-and". For the parallel corpus and monolingual corpora, we obtained word classes using the mkcls tool 6 with 50 classes. After getting the original features and the transformed features, we used the binary logistic regression (maximum entropy model) implemented in the Classias toolkit 7 to train the MERM.

We used SRILM toolkit 8 to train a 4-gram language model on the Xinhua portion of Gigaword corpus. Our decoder is a state-of-the-art SMT system which adapts BTG to phrasal translation and equips itself with a MERM [Xiong et al., 2006]. During decoding, we performed minimum-error-rate (MERT) training to tune feature weights of the log-linear model [Och and Ney, 2003]. The translation quality is evaluated by case-sensitive BLEU-4 [Papineni et al., 2002] and NIST [Doddington, 2002]. Finally, we conducted paired bootstrap sampling [Koehn, 2004] to test the significance in BLEU score differences.

We chose the modified Huber loss [Ando and Zhang, 2005] as the loss function, and used stochastic gradient descent

2 http://blog.sohu.com/

3 http://u.cs.biu.ac.il/ koppel/BlogCorpus.html

4 http://nlp.stanford.edu/software/corenlp.shtml

5 http://www.fjoch.com/GIZA++.html

6 http://www-i6.informatik.rwthaachen.de/Colleagues/och/ software/mkcls.html

7 http://www.chokkan.org/software/classias/

8 http://www.speech.sri.com/projects/srilm/download.html

(SGD) algorithm to train auxiliary predictors. Following Prettenhofer and Stein [2010], we empirically set the number of iterations and the regularization parameter as 106 and 10-5 for SGD, respectively. We empirically set ϵ1 = ϵ2 = 1000, sl = sr = 3, and used the Lanczos algorithm implemented by SVDLIBC 9 to compute the SVD of the dense parameter matrix W, similar to Blitzer et al. [2006]. In this process, negative values in W were set as 0 to yield a sparse representation.

4.3 Result and Analysis

Various Factors on Classification Results

From Step 2 in Section 3.2, we know that the pivot feature number m and reduced dimensionality k play important roles in our method. The former determines the quality of the correlation between different domains, and the latter controls the representation of transformed features. In this section, we try different settings for these parameters based on experiments of reordering classification on the development set.

In our implementation, we first word-aligned all 4192 parallel sentences in the development set together with original training corpus, and then extracted reordering examples with their source-side lengths ranging from 2 to 15. Table 3 summaries distribution of phrase orientations (straight or inverted) over different lengths. From development set, we find that: 1) all distributions of the straight and inverted orientation are imbalanced, especially when the length is small; 2) the number of instances shrink with the growth of length. Inspired by these observations, we chose F-measure as our metric for reordering classification (phrase orientation prediction) accuracy, and conducted experiments separately on each length for classification.

We trained two reordering models: one is the conventional model with only original reordering features; the other is the improved model with the original and transformed reordering features. Considering the effect of different factors, we implemented our approach using different numbers of pivot features (from 100 to 400 with an increment of 100 each time) and reduced dimensions (from 60 to 120 with an increment of 20 each time) following previous work on structural learning [Blitzer et al., 2006; 2007; Prettenhofer and Stein, 2010].

Results are shown in Figure 3, from which we observe that the utilization of the transformed features can improve reordering significantly under most settings. The F-measure for both our model and baseline decreases as phrase length increases. This indicates that the reordering problem is more serious for long phrases. However, compared with the baseline, our adaptive model falls more slowly, and maintains better generalization in domain weblog. Intuitively, our model performs better than the baseline when phrase length ranges from 5 to 11.

9 http://tedlab.mit.edu/˜dr/SVDLIBC/

We further show overall performance of all reordering instances in Table 4. On the one hand, our model is consistently better than the baseline. The absolute improvement is small, this is mainly due to the large proportion of short phrases of which the F-measure in the baseline is already very high (over 90%). On the other hand, we do not see consistent improvement with the growth of the pivot feature number and dimensionality. This suggests that our model is insensitive to the change of m and k in a relatively large range. Such insensitivity resonates with the finding of Ando and Zhang [2005].

Roughly, our model performs well when the pivot feature number ranges from 200 to 300, and the dimensionality from 80 to 100. Considering the tradeoff between performance and efficiency, we conducted SMT experiments setting the reduced dimension to 80 and the pivot feature number to 200.

Translation Results

With the optimal hyper-parameter configuration found on the development set, we evaluated our method on the Chinese-toEnglish translation task on the test set. In addition to to baseline system, we also compared against another two methods that also focus on the exploitation of monolingual resources.

• Additional Language Model: Since a huge amount of in-domain monolingual corpora are available, we trained an additional language model with this monolingual resource, and expected better adaptation of this additional language model to the in-domain data.
• Transductive Learning Model: Inspired by the transductive learning method [Ueffing et al., 2007], we retrained our reordering model. We used importance sampling to select 10,0000 sentence pairs over 20-best lists, based on length-normalized sentence scores.

Table 5 summaries the results. The enhanced system consistently outperforms the baselines. Using our method, the BLEU/NIST scores of the SMT system are 17.71/6.2121, which obtain 1.59/0.6914, 0.41/0.4628 and 0.76/0.4234 Bleu/NIST points over the baseline system, the system with additional language model and the system using transductive learning, respectively. Our approach outperforms the other three methods, and all these improvements are statistically significant (p<0.01, p<0.05 and p<0.01, respectively) verified by the significance test tool developed by Zhang et al. [2004].

We further aligned all 2664 parallel sentences on the test set together with the original training corpus, and extracted reordering examples to see how different models perform. The data statistics is also given in Table 3, and the classification result is shown in Figure 4. Our model outperforms both the baseline and TLM, and performs well for long phrase reordering prediction. During decoding, our model will greatly benefit from the higher prediction accuracy of long phrase reordering. This further demonstrates the advantage of our model over baselines in that our model can generalize better to in-domain data.

5 RelatedWork

Domain adaptation for SMT has attracted considerable attentions in recent years. Previous studies have mainly focused on the adaptation of translation model and language model, while we pay attention to the adaptation of a discriminative reordering model, which has attracted little attention before.

Previous methods either focus on the collection of indomain bilingual data, or exploit relations between different domains. Some researchers use transductive learning to translate in-domain monolingual data with an SMT system, and use these translated data as additional training data [Ueffing et al., 2007; Bertoldi and Federico, 2009]. Data selection approaches [Axelrod et al., 2011; Duh et al., 2013] are also used to search for bilingual sentence pairs that are similar to the in-domain data set. The key idea of these approaches is to create in-domain sentence pairs for SMT systems.

Different from the above-mentioned work, many other researchers focus on the studies of assigning appropriate weights to sentences or phrase pairs from training corpus [Matsoukas et al., 2009; Foster et al., 2010; Sennrich, 2012; Hoang and Sima'an, 2014]. With respect to the adaptation of reordering model, Chen et al. [2013] adopts linear mixture model technique. The correlations between different domains are explored in their reordering model, which, different from ours, is based on parallel corpora.

Compared to the above approaches, we directly exploit correlations between different domains by utilizing monolingual data without collecting parallel corpus. The idea of our method is related to Cui et al. [2013], who explore multi-task learning to jointly adapt SMT models to multiple domains by leveraging the common knowledge shared by different domains. The difference is that we focus on the adaptation of reordering model, and adapt structural learning to DRM.

6 Conclusion

In this paper, we present a structural learning based adaptive DRM for phrase-based SMT. We first apply structural learning on the monolingual data from different domains to obtain correlations between reordering features of different domains. A MaxEnt-based DRM is trained on the out-ofdomain corpus that incorporates the learned correlation information. Experiment results have shown that our approach achieves significant improvements over a variety of baselines.

In the future, we plan to continue our work in the following aspects. First, since our approach is general to other DRMs, we will apply it on other SMT systems. Second, we will explore better methods to optimize important parameters such as the pivot feature number and the reduced dimension.

Acknowledgments

The authors were supported by National Natural Science Foundation of China (Grant Nos 61303082 and 61403269), Natural Science Foundation of Jiangsu Province (Grant No. BK20140355), Natural Science Foundation of Fujian Province (Grant No. 2013J01250), Research Fund for the Doctoral Program of Higher Education of China (No. 20120121120046), and the Special and Major Subject Project of the Industrial Science and Technology in Fujian Province 2013 (Grant No. 2013HZ0004-1), and 2014 Key Project of Anhui Science and Technology Bureau (Grant No. 1301021018). We also thank the anonymous reviewers for their insightful comments.