2 Existing schemes for Phrase Table reduction

A significant amount of work has already been done for Phrase Table reduction and maintaining the translation quality simultaneously. The approaches can be broadly categorized as follows:

1. (1) Input-specific filtering of the phrases based on the input text that is to be translated.

2. (2) General approaches of filtering without the advance knowledge of the input text.

Koehn (Reference Koehn2004) proposes a scheme where the input source sentences are analyzed, based on the phrase pairs that are selectively loaded in the memory. A more sophisticated approach in this direction is described in Badr et al. (Reference Badr, Joanis, Larkin and Kuhn2007), where the relationship between different translation models are considered for obtaining a much smaller set of phrases associated with each sentence to translate. With this approach, about fifty-nine per cent reduction of the Phrase Table is achieved.

These schemes thrive upon the underlying policy that only the phrases that can contribute for the translation of a given input sentence are filtered. This helps in maintaining the translation quality. On the other hand, these schemes cannot be used for generating the translation of sentences in general, because the pruning mechanism is based on the specific input text to be translated, and therefore is not a source-independent mechanism.

In the second group of approach where the advance knowledge of input text is not considered for the Phrase Table Pruning, the motivation is to identify the phrase pairs that are redundant. Redundancy of entries in the Phrase Table can be due to the following:

1. (1) Phrase pairs that do not add to the quality of the translation results. This means the phrases do not have a value addition in the translation results. Their retention or omission in the Phrase Table does not affect the quality of the output translation.

2. (2) Phrases that may lead to erroneous translation outputs. These are the phrase pairs which do not provide an appropriate/usable translation of the source phrase.

Consequently, removal of those phrase pairs is not expected to degrade the performance of the system. On the other hand, their omission should reduce the memory and processing requirements of the translation system. Sections 2.1–2.3 provide some broad classification of the techniques for pruning a Phrase Table.

2.2 Significance pruning

Significance pruning is used for testing whether the chance of co-occurrence of a source-target phrase pair is higher than they occur together ‘just by-chance’ (Johnson et al. Reference Johnson, Martin, Foster and Kuhn2007). The following statistics help to derive a 2 × 2 contingency table, as shown in Table 3, for a phrase pair

• • Count of source phrase N (f).

• • Count of target phrase N (e).

• • Co-occurrence count of source and target phrase N (f, e).

• • Number of sentences in the bilingual corpus N.

Table 3.

Two-by-two contingency table for a phrase pair (f, e)

Thereafter, the probability of the phrase pair occurring together is calculated using a hypergeometric distribution as follows:

(3) \begin{equation} p\left( {N(f,e)} \right) = \frac{{\left( \begin{array}{@{}l@{}}N(f)\\ N(f,e) \end{array} \right)\left( \begin{array}{@{}l@{}}N - N(f)\\ N(e) - N(f,e) \end{array} \right)}}{{\left( \begin{array}{@{}l@{}}N\\ N(e) \end{array} \right)}} \end{equation}

If the probability is less than a pruning threshold, which is determined experimentally based on the reduction of the Phrase Table required, the phrase pair is pruned.

3 Proposed solution for Phrase Table pruning

The proposed scheme of parallel phrase pair filtering uses the syntactic information of the source language (Hindi) and the Marker information of the target language (English) together to reduce the size of the Phrase Table. The scheme focusses on finding the redundant phrases which do not add to the quality of the translation. Redundant phrases are those phrase pairs that can be derived from various combinations of other phrase pairs as well. Hence, this scheme is an extension to the entropy-based pruning technique using the syntactic information of the source and the target language pair.

A ‘syntactic phrase’ is defined as a word sequence covered by a single subtree in a syntactic parse tree (Imamura Reference Imamura2002). Many different language parsers are available that parse a given input sentence, and output the generated phrases, such as Noun Phrase, Verb Phrase. In our work, we used the LTRC Shallow ParserFootnote ³ for Hindi which gives the analysis of a sentence in terms of morphology, POS tagging, Chunking and few others. Apart from the final output, it also provides the intermediate output of individual modules. All outputs are given in Shakti Standard Format (Bharati, Sangal and Sharma Reference Bharati, Sangal and Sharma2007). For illustration, given the Hindi input sentence,

the LTRC Shallow Parser generates the following Syntactic Phrases:

1. (1) (raam ne)→Ram

2. (2) (ravi ko)→Ravi

3. (3) (apne ghar par)→to his house

4. (4) (khaane)→food

5. (5) (khaane ke liye)→to eat

6. (6) (bulaayaa thaa)→ had called

On first analysis and study of limited examples, a system designer tends to feel that syntactic phrases are the key to machine translation using phrases. Hence, a realistic general tendency is to retain only syntactic phrases and discard all other phrases from being considered in the Phrase Table. However, Koehn et al. (Reference Koehn, Och and Marcu2003) showed that restricting phrasal translation to only syntactic phrases yields poor translation performance – the ability to translate other phrases (such as ‘there are’, ‘note that’ and ‘according to’) turns out to be critical. Similar translation issues exist for Hindi phrases as well which do not form a part of the syntactic category. For example, (jaise kii) →like, (kahte hai ki) →said that.

For such phrases, literal translation (e.g. (kahte hai ki) → that is to say) is not appropriate. Hence it is imperative that such phrases should be considered completely, and not as sub-parts like (kahte), (hai ki). The correct translation of such phrases is important because of the high frequency of these appearing in Hindi texts.

In the proposed approach, the knowledge of the source and target language sentence structure is used to identify the useful phrase pairs, and discard the rest of the Phrase Table entries. For the source language, Hindi in our case, the syntactic phrases are considered as indicators of valid phrase construct. For this purpose, a Hindi Shallow Parser generates the syntactic phrases.

For the target language, i.e. English, the Marker words (Sánchez-Martínez and Way Reference Sánchez-Martínez and Way2009) (e.g. prepositions, pronouns, articles) indicate the boundary of English phrases. This is based on the Marker Hypothesis (Green Reference Green1979) which states that “there is a closed set of words that provide the structure for the remaining words in a sentence, to express their meaning”. This means that the syntactic structure of a language is marked at the surface level by a closed set of Marker words, and the proposed scheme takes the advantage of the Marker words to identify the phrase boundaries of the English sentence.

The following is the proposed scheme for identifying phrase pairs that should be retained in the Phrase Table. The rest of the phrases are pruned.

• • Step1: Syntactic phrases are generated for the input Hindi sentence and the resulting phrases are retained. This implies that the parallel phrases that contain one or more complete syntactic segment for the Hindi sentence are retained.Footnote ⁴

• • Step2: For the Hindi phrases obtained in Step1 corresponding English translations are retrieved from the Phrase Table. There are cases when multiple English phrases are mapped to the same Hindi Phrase. Out of the set of these phrase pairs only those are retained in which the English Phrase starts with a Marker word. This choice is based on the Marker Hypothesis stated above. Note that the Marker boundary to be defined for the starting and ending of the phrase will make the technique more restrictive. Because of this reason we only chose to retain phrases starting with Marker word.

The following example illustrates the proposed phrase filtering scheme in a systematic manner. Consider the following parallel sentence pair:

(mujhse Mr Rajesh Mohan ke liye reference letter bhi zaroor lekar jaanaa)

→ Also take from me the reference letter for Mr. Rajesh Mohan.

The output from MOSES generates 47 phrase pairs in the parallel Phrase Table from the above sentence. Some useful ones of them are shown in Figure 2. The output of Figure 2 shows the aligned phrases from MOSES and the statistical information for each of them. For the present work, these statistical informations corresponding to every phrase is not relevant and henceforth will not be shown in the output. But many of the outputs generated by MOSES seem meaningless also, as given in Figure 3.

Fig. 2.

MOSES sample output.

Fig. 3.

Redundant Parallel Phrases from MOSES.

To prune the meaningless phrases from the parallel Phrase Table using the proposed scheme, following is the systematic approach using the proposed technique.

• • Step 1: First we should identify the source language (Hindi) syntactic phrases. This is done using the Hindi parser. The parse output of the given Hindi sentence

is shown in Figure 4.

Fig. 4.

Output of hindi parser for syntactic phrases.

The syntactic phrases generated by the Hindi Parser are the following:

1. (1) (mujhse mr) (From)

2. (2) (rajesh mohan ke liye) (for Rajesh Mohan)

3. (3) (reference letter bhii) (Also reference letter)

4. (4) (zaroor) (definitely)

5. (5) (lekar jaanaa) (take)

• • Step 2: In this step, the Marker information of target language (English) is used. The Marker words in the given English sentence are: ‘from,’ ‘me,’ ‘the’ and ‘for.’

Using the above two steps, only those phrases are retained for which

1. (1) the Hindi part has one or more complete syntactic phrase (Step 1), and

2. (2) the English counterpart starts with a Marker word (Step 2), and

for example, some of the phrase pairs that are retained are listed in Figure 5. The complete set of twenty-eight phrase pairs retained out of the forty-seven phrase pairs is mentioned in Appendix A.

Fig. 5.

Example phrases retained after pruning scheme.

After applying the proposed filtering scheme that uses the syntactic structure for Hindi and marker words of English, the number of phrase pair for the given parallel sentence pair reduced from forty-seven to twenty-eight. Thus there is almost 40 per cent reduction in the Phrase Table size. This scheme is applied on UMC002-English Hindi parallel corpus having nearly 45,000 parallel sentences and IIT Bombay English–Hindi Corpus containing 1.49 million parallel sentences and the BLEU score is measured to observe the effect of reduction of Phrase Table entries in the translation quality. The details of the experiments and the results are given in Section 4.

4 Experiments for Phrase Table pruning

For conducting the experiments to evaluate the proposed pruning technique, two Hindi English parallel corpuses have been used.

The first is UMC002 (Bojar et al. Reference Bojar, Stranák, Zeman, Jain and Damani2010) and is published by Charles University in Prague, UFAL. It contains nearly 45,000 parallel sentences. Apart from that, there are parallel tokens for both the languages. These tokens are obtained from Wikipedia named entries for the years 2008 and 2009. The tokenization was performed for all the source sentences using the Trainable Tokenizer. Parallel phrases have been extracted from the UMC002 using the MOSES toolkit.

The second parallel corpus is the IIT Bombay English–Hindi Corpus (Kunchukuttan, Mehta and Bhattacharya Reference Kunchukuttan, Mehta and Bhattacharyya2017). The corpus has been compiled from various existing sources available in public domain (primarily OPUS (Tiedemann, Reference Tiedemann2012), HindEn (Bojar et al., Reference Bojar, Diatka, Rychly, Stranak, Suchomel, Tamchyna and Zeman2014) and TED (Abdelali et al., Reference Abdelali, Guzman, Sajjad and Vogel2014)) as well as corpora developed at the Centre for Indian Language Technology, IIT Bombay over the years. The corpus contains almost 1.49 million parallel sentences from various domains. Due to the limitation in computing resources, we performed the experiments in three sets (Set 1, Set 2 and Set 3) each containing 450,000 sentences, and finally taken an average BLEU score and computational time for the results.

In both the cases, the MOSES toolkit uses the bi-phrases extracted from GIZA++ word alignment directly. The size of the Phrase Table containing the parallel phrases is almost 6.75 GB for the 40,000 sentences of the UMC002, and almost 96.57 GB for every 450,000 sentences from the IIT Bombay English–Hindi Corpus. The experiments are conducted for six different phrase reduction techniques for reducing the size of the Phrase Table. Statistical machine translation is performed using the MOSES translation engine using the complete and the pruned Phrase Table and the BLEU score (Papineni, Roukos, Ward and Zhu Reference Papineni, Roukos, Ward and Zhu2002) is calculated for measuring the translation quality. Following are the phrase reduction techniques tried in this work:

1. (1) Stratified Phrase pair reduction

2. (2) Phrase length based reduction

3. (3) Entropy-based reduction

4. (4) Source language (Hindi) Syntax-based reduction

5. (5) Target language (English) Marker-based reduction.

6. (6) Combination of Syntactic- and Marker-based technique for reduction

The first three techniques do not contribute to the proposed pruning scheme. The first and second technique is based on the statistical parameters of the Parallel Phrase Table. The third technique is a standard technique of Phrase Table pruning, as explained in Section 2.3. The last three schemes are proposed in this work and contribute to the pruning mechanism. Here, schemes 4 and 5 are combined to get scheme 6. Individually, either scheme 4 or 5 are not resulting in good results hence a combination of them is needed.

Thus, for each of the six phrases reduction techniques the BLEU scores of the translation results of 5,000 test sentences are obtained. Note that for the UMC002 corpus out of the 45,000 parallel sentences, a set of 40,000 parallel sentences are used to prepare the training data. Similarly, for every run of the IIT Bombay Parallel Corpus 450,000 parallel sentences are used for preparing the training data. For both the corpuses, these numbers include the 500 sentences used for tuning the MOSES system using the minimum error rate training (Och, Reference Och2003) tuning algorithm. A set of 5,000 sentence pairs are used for testing which are not a part of the training and tuning data set. The details of the experiments are given from Sections 4.1–4.6.

4.1 Stratified phrase pair reduction

In stratified phrase pair reduction scheme, the phrases chosen for reduction are randomly picked from the cluster of phrases generated from each parallel sentence pair. For example, suppose we have a parallel sentence pair of Hindi and English sentences as H1 and E1, respectively. From this parallel sentence pair, we generate forty parallel phrases. For reducing the whole parallel Phrase Table by say ten per cent, we will reduce four phrases chosen randomly from this forty parallel phrases. Similarly, if another pair H2, E2 generates sixty parallel phrases, six of them would be chosen for pruning.

This scheme of clustering the phrases based on the parallel sentence pairs, and reducing evenly from each cluster ensures that the entries in the Phrase Table do not discard any complete sentence pairs. Table 4 shows the correlation of the BLEU score with the reduction of the Phrase Table size for 5,000 sentence translations for UMC002 and IIT Bombay Parallel Corpus.

Table 4.

BLEU score variation with stratified phrase pair reduction

The results of Table 4 show that the resultant BLEU score of the Stratified Phrase Pair reduction scheme is random. This is because of the random selection of phrases being pruned from the Phrase Table and there can be cases of important phrases to be pruned from the Phrase Table.

4.2 Phrase length based reduction

In this scheme, the phrases to be pruned are decided on the basis on the number of words in the phrases. This means that the phrases which have word length greater than a threshold are pruned. Table 5 shows the correlation between the maximum word count of a phrase in the Phrase Table, with the percentage reduction of the Phrase Table, and the corresponding effect on the translation quality.

Table 5.

BLEU score variation with phrase length based reduction for UMC002

As shown in Table 5, by applying the maximum word count of a phrase limitation the size of the Phrase Table is reduced. For illustration, if the maximum word count allowed for a phrase is three, all the phrases from the Phrase Table having word count higher than three are pruned, and the Phrase Table is reduced by seventy-two per cent. With this reduced Phrase Table, the translations generated for 5,000 sentences have BLEU score of approximately 5.4 for the UMC002 Corpus. Similarly, with the same maximum word count allowed for a phrase of three, the Phrase Table for IIT Bombay Corpus is reduced by 66.3 per cent, and the average BLEU score is 6.21 using this reduced Phrase Table.

Tables 5 and 6 show that retention of the long phrases improves the translation quality significantly when the phrases have maximum word count of four. This is shown by the higher increase of BLEU score when max size of phrases is four as against three, whereas the variation remains less significant when the maximum phrase size is made five or six.

Table 6.

BLEU score variation with phrase length based reduction for IIT bombay parallel corpus

Also, Table 5 shows that in the Phrase Table almost twenty-eight per cent phrases are smaller than length four. This is derived from the fact that when we keep the max phrase word limit as three, seventy-two per cent of the Phrase Table is pruned. Hence, twenty-eight per cent phrases are unary, binary or ternary in the Phrase Table. Using this data, we can conclude that there is a significant percentage of phrases which are long (greater than three words) and without retaining those phrases in the Phrase Table the translation quality is significantly poor (BLEU score is approximately six).

4.3 Entropy-based reduction

This is a standard pruning technique as explained in Section 2.3. The authors of this technique have done experiments with Chinese–English and Portuguese–English parallel corpus. For comparisons with the proposed pruning technique, the Entropy-based pruning scheme is implemented for conducting the experiments on Hindi–English parallel corpus.

Table 7 shows the variation of the BLEU score of 5,000 test sentences from UMC002 and IIT Bombay Parallel corpus, with the changing Phrase Table reduction size done by the Entropy-based Pruning technique.

Table 7.

BLEU score variation with entropy-based phrase pair reduction

The variation of the BLEU score with the reduction in Phrase Table size is following a uniform trend in this case. These results are compared to the proposed technique in Section 4.6 and finally in Section 8.

4.6 Combination of syntactic and marker based technique for reduction

The results of Sections 4.4 and 4.5 indicate the effect of using the sentence structure information of the source language and target language to identify the entries of the Phrase Table to be pruned.

In Section 4.4 by considering only, the source language (Hindi) sentence structure information for pruning, the translation system which uses the Pruned Phrase Table lacks the ability to translate non-syntactic portions of the sentence. This is as per the explanation in the Section 3 from the analysis of (Koehn et al. Reference Koehn, Och and Marcu2003) which showed that restricting phrasal translation to only syntactic phrases yields poor translation performance.

In Section 4.5, only the target language (English) sentence structure information is used for pruning. With this the translation quality further worsens as depicted by a BLEU score of 7.5 though the Phrase Table size is 3.91 GB. The dip in the BLEU score indicates that the phrase pairs that result in good quality translation are pruned from the Phrase Table. The reason for this is the difference in the sentence structure between the source (Hindi) and the target (English) language. Unlike similar structured language pairs like English–French and English–Spanish, Hindi–English sentence structure is very different. For similar structured language pairs, the Marker words serve as delimiters indicating phrase boundaries, and can be utilized for pruning the Phrase Table entries as given in (Sánchez-Martínez and Way Reference Sánchez-Martínez and Way2009). Because of the difference in Hindi English sentence structure, there is no direct mapping between the marker-based chunks of English phrase to its corresponding Hindi counterpart. Because of this difficulty, as explained in Section 3, the marker information in the proposed scheme is used only for the cases when multiple English phrases are mapped to the same Hindi Phrase. In such a scenario, only those phrase pair are retained in which the English Phrase starts with a Marker word.

Since the approaches of Sections 4.4 and 4.5 do not individually produce good translation results, they were combined to utilize the source and target language information simultaneously. With the combined approach of Sections 4.4 and 4.5, the Phrase Table is reduced by 72 per cent and 61.48 per cent for UMC002 and IIT Bombay Parallel Corpus, respectively. The BLEU score of the translation of 5,000 test sentences is 22.52 and 14.97, respectively, i.e., much higher than either of the results of Sections 4.4 and 4.5. Tables 8 and 12 show the comparative results obtained by schemes given in Sections 4.4–4.6 for UMC002 and IIT Bombay Parallel Corpus. With similar reduction in the Phrase Table size (72 per cent), the BLEU score of Entropy-based pruning technique for UMC002 is 20.96, which is slightly lesser than the one obtained by the proposed pruning technique. Also, with 61.48 per cent Phrase Table size reduction for IIT Bombay Parallel Phrase Table, the BLEU Score of Entropy-based pruning technique is 14.01.

Table 8.

BLEU score variation with no pruning, syntax based, marker based and combined scheme for UMC002

Table 9.

BLEU score variation with no pruning, syntax based, marker based and combined scheme for IIT bombay parallel corpus set 1

Table 10.

BLEU score variation with no pruning, syntax based, marker based and combined scheme for IIT bombay parallel corpus set 2

Table 11.

BLEU score variation with no pruning, syntax based, marker based and combined scheme for IIT bombay parallel corpus set 3

Table 12.

BLEU score variation with no pruning, syntax based, marker based and combined scheme for IIT bombay parallel corpus average

As shown in Table 8, for UMC002 corpus without using any pruning technique and utilizing the complete 6.75 GB of parallel phrases the translation BLEU score was 23.98. This shows that with the parallel Phrase Table size being reduced by 72 per cent, the translation quality has a minor dip of 1.46 BLEU score. Having a reduced Phrase Table size requirement can be useful for real-time translation systems, where the pruned parallel Phrase Table can help in getting faster results due to lower computational overhead. The comparison of average translation time for Hindi sentences with various Phrase Table pruning techniques are mentioned in Section 8, where a complete translation system is explained using the proposed and the Entropy-based pruning.

5 Existing schemes for similarity measurement

Once the Phrase Table is prepared, and the redundant entries are pruned, the next step for translation is to have a phrase similarity measurement metric. Using the phrase similarity metric, phrases similar to the input phrase are obtained from the Phrase Table to derive the translation of the input sentence. Various schemes for similarity measurement for a complete sentence are available in literature, but none of them is specific for sub-sentence (or phrase) level similarity. Nevertheless, they provide a broad level understanding of the techniques to identify similarity between two sentences. They can be categorized as follows:

6 Proposed solution for similarity measurement

Once the Phrase Table contains the filtered entries, an SMT scheme generates phrases from the input sentence to be translated. The input sentence phrases are compared with the phrases in the filtered Phrase Table to find the similar parallel phrases. The translations of the identified similar phrases are used for generating the translation of the input sentences’ phrases. As discussed in Chatterjee (Reference Chatterjee2001) similarity measurement between sentences for a translation system can be defined in three ways:

1. (1) Semantic – refers to thesaurus or dictionary-based similarity i.e., sentences having same or similar words.

2. (2) Syntactic – where structural similarity is used for measurement of similarity between sentences.

3. (3) Pragmatic – where two sentences having the same practical significance are considered similar.

Taking the cue from the above, we propose to utilize the above metrics for phrases as well. However, in the proposed approach we use only the syntactic and semantic factors, and a hybridization of them. In the proposed approach proper weights (i and j) have to be assigned to the similarity values generated by each of the factors (semantic and syntactic similarity), to get a final similarity score. The weights (i and j) are experimentally determined to maximize the precision of the retrieved phrases with the condition that i+j = 1. The algorithm for calculation of the similarity metric between any two phrases is given in Figure 6. The algorithm mentioned in Figure 6 uses Hindi WordNet Based Similarity and Syntactic Phrase Similarity to calculate the total Phrase Similarity. If the phrases under consideration for similarity are not of the same syntactic type the similarity score is 0. The details of each of the different similarity criterion are explained in Sections 6.1 and 6.2.

Fig. 6.

Algorithm for similarity measurement for any two phrases.

6.1 Hindi WordNet based similarity

The Hindi WordNetFootnote ⁸ (Bhattacharyya Reference Bhattacharyya2010) is a system for bringing together different lexical and semantic relations between the Hindi words. This is similar to the concept of English WordNetFootnote ⁹ developed by Ted Peterson, which is a large lexical database of English. Nouns, verbs, adjectives and adverbs are grouped into sets of cognitive synonyms (synsets), each expressing a distinct concept.

Given two Hindi words w ₁ and w ₂, the semantic similarity between them is calculated in the following way:

1. (1) Path Length: the semantic distance between two words in the word net graph. The Path Length from w ₁ to w ₂ can be determined using the algorithm given in Figure 7. Obviously, if w1 and w ₂ are two distinct words then

   (4) \begin{equation} \sum \limits _{i = 1}^n {\sum \limits _{j = 1}^k {{s_{ij}}} } \end{equation}

2. (2) Depth of the common ancestor: Consideration of the depth of an ancestor in a WordNet graph as a similarity metric is based on the idea that the words that share a deeper common ancestor in the WordNet graph are more similar than the words for which the common ancestor is more close to the root of the WordNet graph. This is because as the WordNet graph node become deeper (far from the root); the word categories become more specific. Hence, the deeper the common ancestor in the WordNet graph of the words w ₁, w ₂, the higher is their similarity.

Fig. 7.

Algorithm for calculating WordNet-based semantic distance.

Based on the above two factors, the similarity of words in the two Hindi phrases under consideration is calculated. The Total WordNet-based similarity between two words w ₁and w ₂ is

(5) \begin{equation} 2*{\rm {max}}\;{\rm {depth}}\;{\rm {of}}\;{\rm {Word}}\;{\rm {Net}}\;{\rm {Tree}} - {\rm {len}}(w1,w2) + {\rm {depth}}\;{\rm {of}}\;{\rm {commonancestor}}(w1,w2) \end{equation}

For computing the similarity between two phrases P1 and P2, consisting of words w ₁. . .w _n and v ₁, . .v _k, respectively, first the similarity s _ij between each pair of words (w _i, v _j) is computed as above. The similarity between P1 and P2 is computed as

(6) \begin{equation} \sum \limits _{i\, = \,1}^n {\sum \limits _{j\, = \,1}^k {{s_{ij}}} } \end{equation}

6.2 Hindi syntactic phrase similarity

The Hindi syntactic phrase similarity is calculated by identifying the syntactic type of the phrases under consideration. The current work identifies the syntactic similarity for the noun phrase and verb phrase. Once the syntactic type of the phrase under consideration is identified using the LTRC shallow parser, the corresponding similarity metric is calculated. The following section explains the details of calculating the noun phrase and verb phrase similarity value.

6.2.1 Noun phrase similarity

In Hindi, as is in English, there are five types of nouns namely:

(vyakti vaachak sangyaa) [Proper Noun],

(jaati vaachak sangyaa) [Common Noun],

(bhaav vaachak sangyaa) [Abstract Noun],

(samudaay vaachak sangyaa) [Collective Noun] and

(dravya vaachak sangya) [Material Noun]. In that respect Hindi is very close to English. However, in dealing with nouns Hindi has its own characteristics that make translation from Hindi to English challenging. These are:

(ling) [Gender],

(vachan) [Number] and

(kaarak) [Case]. Each of these cause declensions in the Hindi nouns as explained below:

1. (1) (ling) [Gender]. Unlike English, Hindi grammar supports only two types of genders: Masculine, Feminine. So all nouns of neuter gender are categorized with masculine or feminine. Moreover, the categorization is somewhat arbitrary. For example, ‘rice’ in Hindi is masculine, but ‘bread’ in Hindi is feminine. Furthermore, in Hindi the verb of a sentence is modified according to the gender, number and case of the subject. However, as in English the gender of a noun does not play any role in verb modification, unlike in Hindi, therefore, for similarity measurement from Hindi to English text translation gender of a Hindi noun does not play any role. Hence in our approach for Hindi to English machine translation the other two factors i.e., vachan and kaarakare used for similarity measure.

2. (2) (vachan) [Number]. As in English, Hindi also has two types of numbers: singular and plural. The number of the Subject noun of the sentence plays a major role in the verb modification. For illustration, consider the following sentences:

• 

Here, (daud rahaa hai) [is running] is the verb for a singular noun Subject, (baalak)[boy], whereas the verb (daud rahe hain) [are running] is the verb for the plural form (kai baalak) [Many boys].

1. (3) (karak) [Case]. In Hindi the following type of case declensions exist

• • (kartaa) [Nominative] – represented by Hindi word ne

• • (karm) [Objective, Accusative] – ko

• • (karan) [Instruments] – se, ke dwara

• • (sampradaan) [Dative] – ko, keliye

• • (apadaan) [Ablative] – se

• • (sambandh)[Genetive, Possessive] – ka, ki, ke

• • (adhikaran) [Locative] – me, par

• • (sambodhan) [Vocative] – Hey!, Arrey!

Since these case declensions are identified based on few words e.g., ne, ko, they help in identifying the structure of a Noun Phrase.

Considering the number and case declensions of noun, given two noun phrases NP1 and NP2, with the head nouns n ₁ and n ₂, respectively, the similarity between NP1 and NP2 is calculated as given in Figure 8. An important difference between Hindi and English nouns is the case of Compound Nouns. In English juxtaposition of more than one noun is often treated as a compound noun (e.g., rubber ball, golf course and database), which may occur separately or joined. However, such compound nouns are missing in Hindi, where appropriate prepositions/postpositions are required to convey the true sense (Balyan and Chatterjee Reference Balyan and Chatterjee2015). In this work, we have not dealt with compound nouns separately.

Fig. 8.

Noun phrase similarity measurements.

6.2.2 Verb phrase similarity

Singh (Reference Singh2003) made a formal classification of Hindi main verbs based on their form and also compared them with English verbs.

1. (a) (saraldhaatu) [Simple root]: These verbs consist of single words. In Hindi (ubalanaa) [boil] is an intransitive verb and (ubaalanaa)[boil] is a transitive verb. English also has these verbs, but the form remains same in both the transitive and the intransitive usage.

2. (b) (samasikdhaatu) [Composite root] is formed from two words which are related to each other in meaning and separated by a hyphen, e.g., (padha-likha) [to become literate].

3. (c) (mishrakriya) [Complex verb] is formed by combining a noun or an adjective with a verbalizer (kar) [do] or (ho) [do]. For instance, in (taariif karanaa) [to praise], (taariif) [praise] is a noun, and (karanaa) [to do] is a verb.

4. (d) (sanyukta kriya) [Compound verb] is formed with two verbs. The first forms the root and the second takes the tense and aspect information. The verb (ro padanaa) [to start crying] is a compound verb.

While defining similarity between two verbs, the idea is that if the two verb phrases have the same role of the main verb, then they are more similar, as against a phrase in which the main verb plays a different role. For illustration, consider the following three Hindi sentences, and their corresponding English translations

• 

Although sentences S1 and S2 have the same root main verb (khaa) [eat], here S1 and S3 have been assigned the same category of main verb (viz. Compound verb) as per the classification. Hence in our proposed scheme they have been assigned higher similarity. Thus, the similarity value of verb phrases VP1 and VP2 is calculated on the basis of the category of the respective main verbs. It is 1 if they have the same category, otherwise set to 0.

The Total Phrase Similarity is then calculated using the formula given in (7):

(7) \begin{equation} i*{\rm {Word}}\;{\rm {net}}\;{\rm {similarity}}\; + j*\;{\rm {Syntactic}}\;{\rm {Phrase}}\;{\rm {Similarity}} \end{equation}

The values of the relative weights i and j are varied in repeated experiments that is explained in detail in Section 7. For every input phrase, the similar phrases obtained using the similarity metric are checked for precision against the ‘gold standard set.’ We experimented with different values of the weights i and j to obtain the best set of values that maximizes the precision.

7 Experiments for similarity measurement

In order to conduct experiments for similarity measurement a gold standard set of similar phrases is created for each input phrase. By ‘gold standard set’ we mean the set of twenty most similar phrases for a given input phrase. This gold standard set is created with the help of human judges who are linguistic expert of Hindi. Section 7.1 discusses in detail how the gold standard set is created. Section 7.2, on the other hand, explains the details of the evaluation of the proposed similarity measurement technique, where we evaluate to which extent the similarity metric proposed in Section 6 gives the similar phrases that are also found in the above-mentioned golden standard set. The extent of similarity is measured using the average precision value for the similar phrases obtained using the metric proposed in Section 6 with the golden standard set.

7.2 Evaluating the proposed similarity technique

For evaluating the proposed similarity metric, the 1,057 and 1,370 phrases (generated from UMC002 and IIT Bombay Parallel Corpus) and were compared for similarity with the phrases of the pruned Phrases Table, using the scheme proposed in Section 6. Different values of i and j have been used in the Total Phrase Similarity formula (7) by varying them manually in the range (0, 1) so that i + j = 1.

Based on the results obtained by the similarity metric, the corresponding precision is calculated for every input phrase. Tables 13 and 14 illustrate the average precision value using different values of i and j. The value of i and j for which the average precision is maximized is (3/5, 2/5) for the UMC002 corpus. For the IIT Bombay Parallel Corpus value of i and j resulting in the maximum precision is (7/10, 3/10). The impact of translation using the similarity measurement metric with these values of i and j is shown in Section 8.

Table 13.

Weights for similarity measurement and their effect on average precision for UMC002

Table 14.

Weights for similarity measurement and their effect on average precision for Set 1 of IIT bombay parallel corpus

Table 15.

BLEU score, Phrase Table size and average translation time comparison using various techniques for UMC002

8 Overall translation system using the proposed pruning and similarity measurement technique

The proposed Phrase Table pruning mechanism and the similarity measurement technique together is useful to develop a Machine Translation System which is using phrases and the MOSES toolkit of Statistical Machine Translation. The overall system looks as shown in Figure 9.

Fig. 9.

Overall proposed phrase based translation system.

The system is built using the UMC002 and the IIT Bombay Parallel Corpus. The Parallel Phrase Table generated for both these corpuses is pruned using the Entropy based and the proposed pruning scheme explained in Section 4.6. Thereafter, a set of 5,000 test sentences (which are not a set of the training data) are passed into the translation system.

The impact of the proposed similarity measurement scheme explained in Section 7 is also considered in the translation system in the following manner. Phrases are generated for the input sentences, and for each input sentence phrase, similar phrases are extracted from the parallel Phrase Table using the proposed similarity scheme.

The top twenty similar Phrase Table entries for each input phrase are then considered as translation example, and fed into the MOSES translator for translation output generation. To illustrate the same, consider that for a given input sentence ‘n’ phrases are extracted. For each of the ‘n’ phrases twenty similar phrases are extracted from the pruned Parallel Phrase Table, making a set of n ×20 parallel phrases. These n ×20 parallel phrases now comprise the new limited Phrase Table for the MOSES decoder for generating the translation of the given input sentence. Note that the proposed translation system is utilizing the language model and the tuning information from the MOSES setup; hence the recombination of the phrases and the smoothening of the output generated is taken care by the MOSES toolkit. Following are the versions of the supporting tools needed to run the MOSES decoder:

• • GIZA++ and mkclsFootnote ¹⁰: Google Code 1.0.2

• • SRI Language Model Toolkit (SRILM)Footnote ¹¹: 1.5.7

• • IRSTLMFootnote ¹²: 5.20.00

• • MOSESFootnote ¹³: -r 2014 from svn

The overall system is used for a comparative analysis of the following experimental setups:

1. (1) Pure SMT MOSES translation (Setup 1): In this experiment, the MOSES translation system is used on the complete training data without any pruning mechanism for translating the test sentences.

2. (2) Proposed Pruning and Proposed Similarity Measurement (Setup 2): In this experiment, the combination of the proposed pruning mechanism and the proposed similarity measurement technique is used.

3. (3) Entropy-based Pruning (Setup 3): In this experiment, the parallel phrase table is pruned using the Entropy-based technique. No additional similarity measurement technique is applied on the top of it, and the pruned Phrase table is used as an input to the MOSES translator.

4. (4) Proposed Pruning Technique Only (Setup 4): In this experiment, the parallel Phrase Table is pruned using the proposed pruning technique. No additional similarity measurement technique is applied on the top of it, and the pruned Phrase Table is used as an input to the MOSES translator.

The results from the above experiments are compared based on the following factors. Table 10 presents the results in a concise manner for comparison for UMC002. Tables 16–18 present the results for each set of 450,000 sentences of IIT Bombay Parallel Corpus, and finally Table 19 presents the average result of the IIT Bombay Corpus.

1. (1) Phrase Table Size: The complete Parallel Phrase Table of 6.75 GB (for UMC002) and an average size of 96.57 GB (for IIT Bombay Parallel Corpus) are used for the Baseline comparison. The pruned Phrase Table using the Entropy based and the proposed pruning scheme reduces the Phrase Table size by 72 per cent (1.89 GB) and 61.5 per cent (37.19 GB) from the original size.

2. (2) Quality of Translation: BLEU score is used to measure the translation quality of the four setups mentioned above. The best translation quality (23.98 and 16.58 BLEU Score) is achieved when the complete Phrase Table data is used for the MOSES translator. However, for the case of UMC002 the results from Setup 2, is having a minor dip of 0.53 BLEU Score (2.2 per cent), with an appreciable improvement in translation time (6.4 times faster). When the quality of translation is compared for Entropy based (21.90) and the proposed pruning technique (22.52) in Setup 3 and 4, it is observed that the result with Setup 4 is better by 0.62 BLEU score. Similar trend is also observed for the IIT Bombay Parallel Corpus as can be seen in Table 19.

3. (3) Translation Time: The maximum translation time (90 sec/100 sentences) is required when no pruning mechanism is used. This is because the translator has to process the complete 6.75 GB of Phrase Table data to generate the results. When the Entropy-based pruning and proposed pruning mechanism is used in Setup 3 and 4, respectively, the translation time is significantly reduced to 3.5 sec/100 sentences (and 7.16 sec/100 sentences for IIT Bombay Parallel Corpus). This indicates that the pruned Phrase Table can be used to generate translation results much faster.

Table 16.

BLEU score, Phrase Table size and average translation time comparison using various techniques for IIT bombay parallel corpus set 1

Table 17.

BLEU score, Phrase Table size and average translation time comparison using various techniques for IIT bombay parallel corpus set 2

Table 18.

BLEU score, Phrase Table size and average translation time comparison using various techniques for IIT bombay parallel corpus set 3

Table 19.

BLEU score, Phrase Table size and average translation time comparison using various techniques for IIT bombay parallel corpus average

Tables 15–19 also show the maximum and minimum translation time, and their standard deviation. With the experiments of the proposed pruning mechanism (Setup 2 and Setup 4), the standard deviation of the translation time is 2 and 0.25 sec, respectively. The low standard deviation is an indicator that the average translation time is a true reflection of the translation time of the sentences, and hence can be relied on well. Hence, the proposed pruning technique is helping to achieve a better translation quality (as against the Entropy-based pruning technique) in a much lesser time (than the baseline non pruned Pure SMT translation).