Lexical Based Reordering Models for English to Telugu Machine Translation

The methodology of this work focuses on various technical aspects such as word alignment, reordering mechanisms, n-gram findings etc. The word alignment is a major aspect in MT for identifying word-to-word references in a pair of sentences. The fundamental task of this alignment is to detect the relation among the words of sentence given as input in various languages. On the other hand, reordering also equally plays a key role in rearranging the sentence in target language. It maintains efficiency and quality of the sentence.

This section deals with dividing a sentence into group of phrases under Section 3.1., language translation based on word alignment matrix is given in Section 3.2., heuristic based approaches using union or intersection operations are discussed in Section 3.3., various re-ordering mechanism required for language translation is given under Section 3.4., and the parts of the lexical model is discussed in Section 3.5. All these sections show about the working procedure of LBRSM in detail. The development of reordering models is discussed under Section 3.6. The summary of the dataset used in this study is given in Section 3.7

3.1 Formal framework

When a sentence is given as input, it is divided into a group of phrases and direct mapping of phrases is made.

1.png

Figure 1. Dividing the sentence into phrases

Figure 1 describes partitioning of a sentence into sequence of words named as phrases. The probability score is calculated by PBRSM model which is interlinked with pairs of phrases. These scores are stored in pre-defined phrase table. In this work, different parameters of PBRSM model are analyzed to evaluate the effects on quality of sentence translation from English to Telugu language. This is done through a three-step process such as training, translation and testing. In training phase, phrase alignment is identified by giving parallel corpus English as source and Telugu as target language. Then in translation phase, given source sentence is divided randomly into phrases and by using translation table the final target language is obtained. In the final testing phase, the quality of the sentence is identified by reordering the target phrase to get meaningful Telugu sentence.

According to Naïve Bayes theorem [9], deriving the probability of translating English sentence '$e$' into Telugu language '$t$' is formulated in Eq. (1).

$p(e \mid t)=\operatorname{argmax}_e p(t \mid e) p(e)$      (1)

While at the time of decoding, the Telugu sentence '$t$' is divided into group of '$T$' phrases '$t_j^T$'. We consider an equal distribution of probabilities among every feasible division. Every Telugu phrase '$t_j$' in '$t_j^T$' is transformed to English phrase '$e_i$'. A probability distribution is given by '$\varphi\left(t_j \mid e_i\right)$' to represent phrase translation.

An estimate of the absolute distortion distribution of probability '$d\left(\right.$start$_i$, end$\left._{i-1}\right)$' is used to describe the rearrangement of the resulting English phrase. Here, 'start${ }_i$' represent the initial alignment of Telugu sentence which is to be translated into '$i^{t h}$' phrase of English sentence. The resulting position of Telugu sentence is given by '$e n d_{i-1}$' , which is converted into English sentence of $(i-1)^{t h}$ phrase.

To estimate the length of target language, we assume a word cost factor '$\omega$' for every converted English phrase along with '$p_{L M}$' which is an n-gram model language. This can be used to improve the model performance. Generally, to attain distortion for longer outcomes, this value is set to more than 1 .

In brief, the accurate English target sentence '$e_{\text {best}}$' represents a Telugu source sentence '$t$' in accordance with the proposed model is given by Eq. (2).

$\begin{gathered}e_{\text {best }}=\operatorname{argmax}_e \varphi\left(t_j \mid e_i\right) \\ d\left(\operatorname{start}_i, \text { end }_{i-1}\right) p_{L M} \omega^{\text {length }(e)}\end{gathered}$               (2)

The initial translation is carried by '$\varphi\left(t_j \mid e_i\right)$' , reordering of phrases is given by '$d\left(\right.$ start$_i$, $\left.end_{i-1}\right)$' and meaningful and grammatical order of target English phrase is given by '$p_{L M} \omega^{\text {length }(e)}$'.

3.2 Alignment matrix for translation

The main fundamental approach in MT model is alignment of word. This alignment among the words can be identified by word alignment matrix as shown in Figure 2. The size of this matrix is dynamic and the size varies depending up on the input sentence. The black cells in the matrix represents the alignment point among English sentence 'Kapoor is at school now' and Telugu sentence 'కపూర్ ఇప్పుడు పాటశాలలో ఉన్నాడు' . In the sentence there may or may not be alignment points within words. This occurs because of few words in English do not have corresponding clear translation in Telugu language. From Figure 2 it is observed that, the English word 'is' is not aligned in Telugu language.

During the translation phase, it is complex to get word to word mapping from source to target language. It becomes very difficult in case of idiomatic sentences due to new and missing words obtained in input language. In this phase, the alignment of words is complex while reordering, deletions and insertions. If $e_i^E=e_1, e_2, e_3 \ldots e_E$ is a source sentence in English and $t_j^T=t_1, t_2, t_3 \ldots t_T$ is a target sentence in Telugu, which should be aligned by words. The subset '$M$' is a word alignment of the Cartesian product according to the places of words available in input and output sentence is given by Eq. (3).

$M \subseteq\{(i, j)$ where $i=1,2, \ldots E$ and $j=1,2, \ldots T\}$          (3)

2.png

Figure 2. Word alignment matrix

3.3 Heuristic based phrase translation table

The words are positioned in both the ways of conversion process, like from English language to Telugu language and vice-versa. Once after the alignment, different word arrangement heuristics are involved to produce symmetric sequence through the initial two arrangements. The word positioning heuristics originates by the convergence of word positions gathered through this. For enhancing the positions, these are inspected from other places in the combination of these initial arrangements. The convergence and combination of English to Telugu and from Telugu to English word arrangement for a converted sentence is represented in Figure 3 and Figure 4.

The highlighted region or cells in phrase translation table indicates the matched words between English to Telugu language. For better understanding, these matched cells are shown in 'black' color as represented in Figure 3. By converting a sentence from Telugu to English language requires more combination of highlighted cells as shown in Figure 4. The empty cells in both examples represents no mapping between source to target language translation.

3.png

Figure 3. Phrase table for English to Telugu sentence mapping

4.png

Figure 4. Phrase table for Telugu to English sentence mapping

The heuristic alignment of phrase begins with intersection operation of the word orientations produced by these two fundamental approaches such as mappings from English to Telugu and Telugu to English. Then these enhanced connections are aligned by union operation. Figure 5 depicts the union or intersection of aligned points translated from Telugu to English and English to Telugu.

5.png

Figure 5. Aligned points from union/intersection operations

In this work, according to Och and Ney [10, 11] there are eight number of conversions which converts any function into symmetric method in terms of variables. These are helpful in analyzing their effect on English to Telugu conversion standard. Let '$X_2$' define translation of source to target language and '$X_1$' define translation of target to source language from available training data. The eight heuristic conversions are as follows:

1. union: All aligned points are considered by performing union operation on $X_1$ and $X_2$ which is represented as $X_1 \cup X_2$ .
2. intersection: Taking aligned points which are common among $X_1$  and $X_2$ and is denoted as $X_1 \cap X_2$.
3. srctotgt: Indicate word alignment obtained from English to Telugu language and is referred as $X_1$.
4. tgttosrc: Indicate word alignment obtained from Telugu to English language and is referred as  $X_2$.
5. grow: The term itself refer gathering the nearby aligned points along with common intersected points of $X_1$ and $X_2$. These points can be taken from any direction like top, bottom, left or right along with union operation.
6. grow-diag: In addition to neighboring points of union operation, in grow function, the aligned points are added from diagonal directions.
7. grow-diag-final: Considering the points in ‘grow-diag’, non-neighboring positioned points among words that are not aligned at least once are also included in this method.
8. grow-diag-final-and: Considering the points in ‘grow-diag-final’, non-neighboring all positioned points that are not aligned are considered in this method.

6.png

Figure 6. Different heuristic conversion functions

By the corresponding positions of alignment point 'A' which is represented by '*' in the form of a matrix is briefed in Figure 6. These eight conversions are used to design a translation model setup by using parallel corpus word alignment toolkit named as 'GIZA++' [18]. The divergent of alignment of grow symmetric function includes corresponding points from both intersection points which are unaligned and union operations. The heuristic approach of symmetric functions is elaborated in the form of pseudo code given by MOSES MT [19] and is shown in Figure 7. This pseudo code defines English '$e$' as target language and '$f$' denotes any foreign source language like 'Telugu' .

7.png

Figure 7. Heuristic approach - Pseudo code [20]

Basically, with the use of different heuristics, the words and phrases in English to Telugu language training corpus data set are aligned. Here the compatible phrase pairs are extricated and possibilities are then allocated to the pairs. The phase pair $\left(e^{\wedge}, t^{\wedge}\right)$ is treated as extricated and these are provided by words i.e., $e_1, e_2, \ldots e_n$ in $e^{\wedge}$ are positioned points by words having in $t_1, t_2, \ldots . t_n$ in $t^{\wedge}$. This can be represented mathematically in Eq. (4).

$\frac{\operatorname{count}\left(t^{\wedge}, e^{\wedge}\right)}{\sum_{i=1}^e \operatorname{count}\left(t^{\wedge}, e_i^{\wedge}\right)}$          (4)

Here $\operatorname{count}\left(t^{\wedge}, e^{\wedge}\right)$ represent the frequency under which the phrases $e^{\wedge}$ and $t^{\wedge}$ are positioned towards each other in the corpus data set.

3.4 Reordering mechanisms

In general, there are two reordering mechanisms such as distance based and lexical based. The distance-based approach maps the words between languages according to the language structure based on distance values. The lexical-based approach positions the words according to the various directions.

3.4.1 Distance based reordering

Phrase reordering at the time of translation process is a dependent approach in terms of language conversions. The morphological structure of English is given by a sequence of subject$\rightarrow$verb$\rightarrow$object whereas in Telugu the sequence is subject$\rightarrow$object$\rightarrow$verb. Therefore, phrase reordering plays a crucial role in maintaining the standards of translation from English to Telugu sentence. This is achieved by calculating the distance mechanism while reordering of phrases and finding the estimates relying on the count of ignored words. The simple reordering mechanism is demonstrated in Figure 8.

3.4.2 Lexical based reordering

It can be done in three types of orientation methods namely monotone, discontinuous and swap. The alignment points that are positioned in the top left directions are called monotone (m).  The alignment points that are positioned in the top right directions are called swap (s). The aligned points that appear neither in top right nor top left referred as discontinuous (d). The orientation methods are represented in the alignment matrix as shown in Figure 9.

8.png

Figure 8. Reordering based on phrase distance

9.png

Figure 9. Reordering based on orientation

These orientation methods are represented in the form of set $(e, t)$ having English as source and Telugu as target languages. For better understanding these orientations are represented in the form of an Eq. (5).

$\left.p_{\text {orientation }}((m \cup d \cup s) \mid e, t)\right)=\frac{\operatorname{count}((m \cup d \cup s), t, e)}{\sum_{(m \cup d \cup s)} \operatorname{count}((m \cup d \cup s), t, e)}$      (5)

where, $\operatorname{count}(m \cup d \cup s)$ provides the frequency of monotone, discontinuous and swap orientations.

3.5 Development of reordering model

The phenomenon of reordering model can be developed in three stages, namely word, phrase and hierarchical. The word based reordering model involves in translating the context language by considering every word. While the phrase based model considers the entire phrase for translating into target language. This development of reordering is done to improve the translation quality by minimizing the error rate.

The requirement to setup a reordering model for words translation distance and lexical based reordering methods are used. From lexical method, we use MOSES lexical reordering models for exploring various combinations.  This model configuration contains five parts in various aspects which are as follows [20]:

1. Modeltype - Defines the kind of model

phrase: model based on phrase

wbe: model based on word

hier: model based on hierarchical order

2. Orientation - Defines corresponding position of model

msd: monotone, swap, discontinuous

mslr: monotone, swap, discontinuous-left, discontinuous-right

leftright: left or right

monotonicity: either non-monotone or monotone

3. Directionality - Defines direction of corresponding position of model

forward: determines next phrase

backward: determines previous phrase

bidirectional: specifies both backward and forward

4. Language - Specifies the language base of model

fe: relies on both input and output languages

5. Collapsing - Specifies how to handle scores

collapseff: Scores are aligned in one direction and are combined into a single feature function.

allff: the scores can be different for each individual function

A total of 25 reordering combinations are used during the model development which contains 1 distance based and 24 lexical based aspects. MOSES toolkit which is available freely is used for training and translation process. For designing our PBRSM model, initially the default weights of the MOSES toolkit are assigned to every factor. Later, along with default parameters all other factors are analyzed in this work.

These 25 reordering factors are combined with 8 heuristic factors for translation of English to Telugu language along with n-gram models are analyzed by using TER and BLEU metrics. To maintain the standards of the language translation we used same dataset for all kinds of models namely 'wbe', 'hier' and 'phrase' .

3.6 Finding probabilities of N-gram

One of the commonly used language models is n-gram, where 'n' represents the number of words in given sentence. This method is used in predicting the next word based on the previous of it in the sentence. For example, bigram means 2 words, trigram means 3 words, 4-gram means 4 words in the given sentence. The main disadvantage of using n-gram method is it require huge size of corpus data. For every next word prediction this method verifies the entire corpus data which is complex. To handle this high volume corpus, we use Natural Language Processing (NLP) to implement n-gram approach [21, 22]. The probability of finding next word with respective to previous words in a sentence is given by Eq. (6)

$p\left(w_n \mid w_1, w_2, w_3, \ldots \ldots w_{n-1}\right)=\frac{\operatorname{count}\left(w_1, w_2, w_3, \ldots \ldots w_{n-1}, w_n\right)}{\operatorname{count}\left(w_1, w_2, w_3, \ldots \ldots w_{n-1}\right)}$      (6)

where, $w_1, w_2, w_3, \ldots \ldots, w_{n-1}$ is the sequence of previous words and $w_n$ defines next word.

3.7 Dataset

Before considering the dataset, it is mandatory to preprocess the raw data. Preprocessing of the dataset can be done in the phase of cleaning. This helps in removing less useful parts present in the sentence by eliminating the commonly use words, duplicates, empty spaces, special characters and other unwanted data.

Table 2. Summary of dataset [23]