Extraction of reordering rules for statistical machine translation

1 Introduction

Reordering of words and phrases is a major challenge faced in statistical machine translation (SMT). Different types of reordering problems are faced for language-pairs of different structures. This paper discusses the problem of reordering and their solutions for English-Hindi language pair, which is a relatively distant language pair. Some of the differences in English and Hindi, as given below, lead to the reordering difficulty:

English is a Subject-Verb-Object language while Hindi is a Subject-Object-Verb language.

In SMT, the language model is responsible for fluency of the translated sentence which takes care of positioning the target words in an acceptable order. But language models also have their limitations. Reordering is introduced after using the language model to handle the problem of language modelling. Reordering is performed using some linguistic rules which are treated as reordering rules here. The reordering rules are also beneficial when dealing with the Out of Vocabulary (OOV) terms in the translation. If a word appears in the source test file, while its translation does not appear anywhere in the monolingual corpus over which the language model is trained. Then selection of the right position of this OOV word in the translated target sentence is a challenge. But if there are some reordering rules and if this OOV term comes under any chunk on which a reordering rule may apply, then the system will place the OOV word at the right position in the translated target sentence. These reordering rules can be extracted manually or automatically. When reordering rules are extracted manually, then experts are required who have linguistic background for the specified language pair. Some of the previous researches used manually extracted reordering rules for improvement in the performance of an MT system.

The objective in this paper is to learn these reordering rules from parallel data in an automatic way. Under this motivation, reordering rules can be extracted in a language-independent manner. As will be detailed in the next section, several researchers have attempted automatic rule extraction technique.

Inspired by previous chunk-level reordering approaches to statistical machine translation, this paper presents an approach to extract the rules from aligned chunk pairs. Here, rules are used to reorder the sentences translated by a baseline SMT system. But these rules are not made by linguist. These rules are extracted by using chunks using the process described in subsequent sections. This approach works well for corpus-based approaches to MT, especially for those language pairs which have scarce-resource and the appropriate parallel corpus is not available.

The rest of this paper is organized as follows. Section 2 describes some related work. Our approach is described in detail in Section 3. Section 4 gives a brief description of the data and the evaluation metrics that were used for the experiments. Section 5 describes the results obtained by the proposed approach and also presents their analysis. The last section contains our concluding remarks.

2 Related work

Reordering is one of the major problems for Statistical Machine Translation (SMT) and increases as the difference in the structure of the languages increases. Distance-based reordering constraints such as IBM constraints [3], distortion limit [4] and local constraints [5] are widely used in phrase based SMT systems. These models give power to phrase-based SMT to solve short distance reordering problem. But, long distance reordering is still challenging.

Some researchers used syntactic information to solve the problem of long distance reordering in SMT but they are mainly useful for the languages with rich morphology to reduce the data sparseness. In [6] Ahsan et al. used a hybrid method which used the features of statistical methods and rule based methods jointly to improve the performance of machine translation for English-Hindi language pair. Neural machine translation is a new area of research, receiving more attention these days [7].

Visweswariah et al. used syntactic trees to extract pre-ordering rules for English-to- Hindi, Spanish, and French translation [8]. Nieβen and Ney used morphological and syntactic information and made transformations to both source and target sentences for reordering in German-English language pair [9]. Popovic and Ney used POS tag information for word reordering in SMT for Spanish, English and German [10]. Word classes are also used to infer new word reordering for improvement in SMT [11].

Collins et al. described a method of using syntactic information in SMT for German-English language pair where they used hand-crafted rules and got 1.6% improvement in comparison to the baseline system [12]. Wang et al. used reordering as a preprocessing step for Chinese to English language pair [13]. When their preprocessing is used in both training and test corpus they observed an improvement of 2.34% in comparison to the baseline SMT system while BLEU score improved only by 0.62 when only test corpus is reordered. Katz-Brown and Collins also performed reordering during preprocessing for Japanese-to-English translation [14]. They reordered Japanese training corpus into an English-like word order before training.

Xu et al. also used precedence reordering approach which is based on a dependency parser. They performed experiments for translation from English-to-SOV languages [15]. This was done for five languages (Korean, Japanese, Hindi, Urdu and Turkish) which have SOV structure. Kim et. al. used syntactic chunks as translation units for Korean to English and Chinese to English Example-based machine translation [16]. They used existing monolingual Chunker to find chunk boundaries and developed a chunk alignment algorithm where IBM word alignment algorithm is applied to chunk alignment by treating a chunk as a word and boosting chunk alignment with word alignment.

Parse trees also give strong information about the structure of the languages. Many researchers used parse tree as the syntactic information for reordering in SMT [12, 18]. But it is hard to build a good quality parser. Genzel used dependency trees to extract source side reordering rules to translate SVO structured languages to SOV structured languages [19]. Zhang et. al. presented two methods to improve the reordering at the chunk level for Chinese-English language pair [18]. By introducing a new lattice weighting factor and by reordering the training source data, the BLEU score improved by 1.4%.

Wang presented a different chunk-based method by treating the translation model as a phrase to string process [20]. Yamada and Knight further extended the model to a syntax-to-string translation modeling [21]. Watanabe et. al. presented chunk-based statistical translation for Japanese-English language pair where the translation model first performs chunking and then each word of the chunk is translated [22]. At last translated chunks are reordered. Recently Neural network-based machine translation system is also proposed [23–25] which could be promising and competitive. Kanouchi et al. used neural reordering model for improvements in phrase-based SMT [26].

Pal and Bandyopadhyay presented a bootstrapping method for chunk alignment in phrase based SMT for English-Bengali language pair [27]. They studied automatic alignments of different types of chunks that boost up the word alignment as well as the machine translation quality. Wu et. al. proposed the use of source chunk-based dependency trees for extraction of pre-ordering rules for translating from Japanese to English language pair and got significant improvement of 1.48 BLEU points in comparison to the baseline SMT system [28]. Pal et. al. performed prior reordering of the source chunks by following the target word order suggested by word alignment for translating from English to Bengali [29]. They reordered the test set by using monolingual PB-SMT built on the original source training data and the reordered source training data. Ding et al. [30] proposed rule-based preordering approach in which they used dependency structure of the source sentences for Japanese-English SMT. They resolved the problem of reordering by pre-ordered the Japanese sentences to English-like order during training and testing phase. They named their method extra-chunk pre-ordering where words can move from one chunk to another chunk [30].

Based on the previous approaches where chunks are used for performance improvement for SMT, this paper also used chunks but in a different way. Here chunks are used at the time of training for rule extraction and at the time of testing for applying these rules on the test sentences. Thus rules are extracted automatically here. The details are given in the next section.

3 Methodology

It is difficult to align words in languages with different structures, due to lower sentence structure agreement and lower word correspondence. Therefore, the translation quality is poor. There is higher correlation at the level of chunks in a sentence pair so we have used chunks to solve this problem. Thus, the translation quality can be improved by aligning chunks and then using them for translation. But direct use of these aligned chunk pairs is not a good idea because the existing tools of chunking sometimes cannot find the perfect chunk boundary which should match in source and target sentences [31]. A pre-processing step is included where words are moved from one chunk to another chunk to match the chunk boundaries for English and Hindi. This is something like extra-chunk pre-ordering proposed by Ding et al. [30] but method is not exactly same.

3.3 Rule extraction

The process of rule extraction is given in Figure 1 Here after performing chunk alignment, we extract “completely aligned chunk pairs”. Here the term “completely aligned chunk pairs” refers to those aligned chunk pairs in which all the words of a chunk of source sentences have their corresponding aligned target word in the corresponding aligned target chunk. After aligning chunks by using the algorithm of chunk alignment given by Srivastava and Sanyal [31], it is not necessary that all aligned chunk pairs are completely aligned. The alignment of all words in source chunk is required to be present in the aligned target chunk since we are extracting rules from the aligned chunk pairs. Therefore, for rule extraction, first completely aligned chunk pairs are extracted and then rules are extracted as described in Figure 1.

OPEN IN VIEWER

Fig.1

The Process of Rule Extraction.

After extracting completely aligned chunk pairs, we extract source side POS tag sequence and position-wise alignment of the words (based on word alignment table given by GIZA++) of these completely aligned chunk pairs and add them in a table. We call this table “Initial Rule Table” because it consists of rules. However, these rules are not the final rules which will be used as a post-processing module with the SMT system. The frequency of occurrence of a rule in those completely aligned chunk pairs is also noted in the Initial Rule Table.

The Initial Rule Table contains a large number of rules but all the rules that appear in this table are not necessarily correct. There are many aligned chunk pairs which consists of a single word on both source and target side. In such cases the rule extracted by those aligned chunk pairs are not useful. These kinds of rules, extracted by those aligned chunk pairs, are discarded and not used further. There might also be some wrong rules due to wrong chunk boundary in the source or target sentences. Moreover, there might be some rules which can work right for some cases but wrong for other cases. The frequency of such rules will be very low and the rules which are working right for most of the cases will have a higher frequency. A small example is given in Figure 1 where a portion of the Initial Rule Table is shown explicitly.

The frequency of occurrence of a rule is denoted by “count” in Figure 1. We filter out those rules which have “count” above some threshold value T and those filtered rules will form the final rule table. The rest of the rules, whose frequencies are lower than the threshold value T, will be discarded. Rottmann and Vogel presented a word reordering strategy for improvements in SMT for English-Spanish and German-English language pairs in which source side is reordered based on Part of Speech (POS) information [33]. Reordering rules are learned from the word aligned corpus. The threshold used by them, to extract the final rules, was 5 and this value was based on relative frequencies of their occurrence in the training data. The present work also uses a threshold value to extract the final rules. However, we do not use a fixed value. Instead, it is calculated from the data and is based on the corpus size.

It needs to be emphasized that we have to be very careful in determining the threshold value because

If the threshold value is very high, then fewer number of rules will be extracted finally which might hurt the performance.

On the other hand, if the threshold value is very low then it will allow extraction of unreliable reordering rules at the final stage which could also degrade the performance.

For example, if we set T as 5 then it might work well for a small corpus but if we train the system on a relatively larger corpus, say with 500K sentence pairs, then we can have unreliable rules due to such a small threshold value. So, we cannot set the threshold to a fixed value.

Our focus here is to get as many correct rules as possible in the final rule table which can be extracted from a given corpus. However, even if the size of the final rule table is not large, it should contain only correct rules. This is because these rules are used for reordering the output of baseline SMT system to improve the translation and any wrong rule can degrade the performance.

The size of the final rule table will depend on the size of the completely aligned chunk pair list extracted from the corpus. Thus, the size of final rule table will depend on the size of the corpus. Thus an expression is determined by keeping all these factors in mind. This expression is used to calculate the threshold value T as given below:

T = | | TNR - NRMC CS / TNR | |(1)

Where

TNR – Total number of rules in Initial Rule Table

NRMC – Number of Rules having minimum count

CS – Size of the parallel corpus (number of parallel sentence pairs in the corpus)

For example, if we consider the small part of initial rule table given in Figure 1. Then the minimum count value is 1 which is the minimum of all the count values in the table. There are two rules which have this minimum count. Thus, NRMC for this table is 2.

We used the above expression for increasing corpus size and the results are given in Table 1. For each size of the corpus, Table 1 shows the number of aligned chunk pairs, size of initial rule table (generated by using aligned chunk pairs) and further size of final rule table (generated by applying threshold T on Initial Rule Table).

OPEN IN VIEWER

Table 1

Threshold value calculated for Different Corpus size

Corpus Size	Threshold T	Number of Aligned Chunks	Initial Rule Table Size	Final Rule Table Size
300	4	300	66	8
600	5	550	111	10
900	6	790	152	12

Since the increase in the corpus size is small, so the change in the threshold value is also small. We can observe that with a corpus size of 300 sentence pairs and with a threshold value (T) of 4 we obtain a Final Rule Table which contains 8 rules. When we increase the corpus size to 600 sentence pairs and with T as 5, we obtain 10 rules in the Final Rule Table. When the corpus size is increased to 900 sentence pairs and with T as 6, we get 12 rules in the Final Rule Table.

Here the final rules extracted from the corpus size of 300 sentence pairs are a subset of the rules extracted from the corpus size of 600 sentence pairs. Similarly, the final rules extracted from the corpus size of 600 sentence pairs are a subset of the final rules extracted from the corpus size of 900 sentence pairs. The count of a longer word sequences is much lower than the count of shorter word sequences. Thus, the finally extracted rules cover those completely aligned chunk pairs which have shorter word sequence or small length. But these small rules improve the translation as can be seen in the example presented in the next section.

3.4 Applying the rules on baseline SMT output

The rules are extracted from the chunk-separated parallel corpus as described above. In this subsection, we will describe the technique for applying these rules to reorder the output of the baseline SMT system in order to improve the translation. The baseline SMT system used here is MOSES [34]. Figure 2 illustrates the process of applying these rules on the output of the baseline SMT system for improving the translation. Here, we are using some other resources too along with the rules, to improve the translation.

OPEN IN VIEWER

Fig.2

Applying rules on the output of baseline SMT system.

These additional resources are the phrase table and word alignment table (generated by GIZA++) which are generated at the time of training the SMT system using MOSES. We also used the word alignment results of IBM Model 1 with POS tag [35] which gives more precise alignments. As explained previously, the extracted rules are based on chunks. Therefore, at the time of applying the rules, we extract those chunks of the source sentences whose POS sequences match with any rule in the Final Rule Table.

If we find a chunk on which a rule may apply, then the aligned target words of the words of source chunk will be extracted from the word alignment table generated by baseline SMT system and POS tagged IBM Model 1. Word alignment tables may align more than one word with a single word. So, the decision for choosing the suitable word for translation will be filtered out by using equation (2).

Returned aligned target words = ( WA 1 ∪ WA 2 ) ∩ Translated Target sentence words(2)

Where

WA1 – Word alignment results returned by GIZA++

WA2 – Word alignment results returned by IBM Model 1 with POS tag

Here the focus is on reordering the output of the baseline SMT system. Hence, we are not changing the translation of any word. At this stage, only the order of words is changed in the translated output. If any source word does not have any translated target word in the translated output. But the source word has some translation available in word alignment tables (WA1 or WA2) with high probability then, that high probability word is inserted here which helps in improving the performance of the system.

Algorithm 1 Rearrange newly translated chunk

Input: Translated Target Sentence (TTS) (Baseline SMT output) and translated target chunks

Output: Modified Target Sentence

1: for each chunk C of Translated target chunks do

2:   Search for the first word of C in Translated Target Sentence (TTS)

3:   if found then

4:    Insert C there and remove all nearby words which match the words of C

5:   else

6:    Search for the next word of C in Translated Target Sentence (TTS)

7:    Go to step 3.

8:   end if

9: end for

After getting the aligned target words, these words are arranged according to the rule selected earlier. The phrase table is one of the files generated by MOSES. It contains phrases and their alignment probability. However, all the phrases generated need not to be correct. Therefore, only high probability phrases are used here for further improvement of the performance of SMT system. Now the output of the baseline SMT system will be rearranged by using Algorithm 1 with the help of the newly translated target chunk and high probability phrases extracted from the phrase table.

As the rules are extracted by using aligned chunk pairs only so each rule can represent a chunk only not the sequence of chunks. Therefore, reordering is applied within chunks only not on overall sequence of chunks.

As per the experiments conducted by Neubig et al. [36], a model performs better when trained on a parallel corpus which is manually aligned in comparison to the model trained using automatically aligned parallel corpus. Even if the size of the automatically aligned parallel corpus is 10 times more than manually aligned parallel corpus, but it does not give good results [36]. Thus, quality of the corpus is more important than the quantity of the corpus. By keeping this fact in mind, we use a small corpus here which is manually created and aligned. Because larger corpus is available now for English-Hindi too, but its quality is not good. We perform translation experiments on the TDIL sample tourism corpus of 1000 sentences for the English-Hindi language pair out of which 900 sentences are used for training, 50 sentences for tuning and 50 sentences for testing.

The results are evaluated by using the BLEU and NIST scores. An open-source toolkit for SMT, called MOSES, is used here as the baseline SMT system. It was developed by Koehn [34] and is used widely by many researchers.

BLEU: IBM introduced the Bilingual Evaluation Understudy (BLEU) score in 2002 [37]. It is determined by finding the matching n-grams between a candidate and reference translation and then calculating the weighted geometric mean. A BLEU score ranges from 0 (the worst translation) to 1 (a perfect translation).

NIST: The NIST (National Institute of Standards and Technology) evaluation metric was introduced in 2002 [38]. It is a modified version of the BLEU score. It may be noted that the BLEU scoring technique gives equal weight to all the n-grams in a modified n-gram precision score. In contrast, NIST gives an informative weight to all n-grams. Thus, the rarer and more informative sequences that exist in the translation contribute more to the final score than the sequences that are more common but less informative. The NIST score is a quality score ranging from 0 (the worst translation) to an unlimited positive value.

5 Results and discussion

As mentioned in the previous section, MOSES is used as the baseline SMT system with the default setting which is a phrase-based SMT system. Table 2 illustrates the results obtained using the proposed method.

Table 2 compares the result of the baseline SMT system with those obtained using each method separately. When chunk based reordering rules are applied to the baseline SMT system, then the BLEU score improved by 0.8% and NIST improved by 0.2 in comparison to the baseline SMT system. When only high probability phrases are used in baseline SMT system the BLEU score results are 1.5% better than the baseline SMT system while NIST improved by 0.1.

When we used both the rules and high probability phrases the BLEU score improved by more than 2.1% and NIST is improved by 0.2 in comparison to the baseline SMT system. When the system is evaluated in terms of NIST, then chunk-based SMT gives the best results over other systems and when the system is evaluated in terms of BLEU then combination of using phrase-table and chunk-based SMT gives the best results.

These results are also compared with the Google translation system which is trained on a huge corpus in comparison to the corpus used in this paper. The BLEU score of the Google translation is better than the baseline system and the proposed method. But when we talk about NIST the proposed Chunk-based SMT gives better results even in comparison to Google translate. Thus, these results illustrate that using these linguistic rules for reordering, which are automatically extracted by using chunk information, we can get better performance even with such a small corpus.

Table 3 illustrates the effect of each system with an example. Here, English glosses are given for each Hindi word (inside the parenthesis ()) in Hindi sentence. English transliteration of each Hindi sentence is also given below the sentence. Here, a rule “[NN NN] [0-0 1-1]” which is extracted by using the proposed method, is applied on “Jaipur city” (a chunk of the example sentence) and the translation gets improved.

OPEN IN VIEWER

Table 3

Translation Example

In this paper, an automatic method for extracting linguistic rules, using chunk information, is proposed. The results of using these rules to reorder the output of baseline SMT system are discussed. Translation results were reported on TDIL sample tourism corpus of English-Hindi language pair of 1000 sentences in which 900 sentences have been used for training, 50 sentences for tuning and 50 sentences for testing. The system is trained and tested on such a small dataset because our goal here is to achieve improved performance with a small corpus.

The BLEU score improved by more than 2.1%. These results even compete with the results of Google translate which has been trained on a very large corpus. The NIST score also improved significantly and is even better than the results obtained using Google translate. Thus, it is concluded that using the proposed method, one can get better results even with a very small corpus.

The linguistic rules which are extracted here are based on chunks of the sentence which further depends on POS tag of the words of the sentences. The tools used for chunking and POS tag are not very good for the chosen target language i.e. Hindi. There is a need of improvement in these tools, especially for Hindi language. If better Chunker and POS tagger will be used, then results might improve further. More analysis on chunk alignment and rule extraction are also necessary. In future, we would try to experiment with the rule extraction method on larger dataset.