# A Relationship: Word Alignment, Phrase Table, and Translation Quality

Authors: Liang Tian; Derek F. Wong; Lidia S. Chao; Francisco Oliveira
Journal: The Scientific World Journal
 (2014)

---

## Abstract

In the last years, researchers conducted several studies to evaluate the machine translation quality based on the relationship between word alignments and phrase table. However, existing methods usually employ ad-hoc heuristics without theoretical support. So far, there is no discussion from the aspect of providing a formula to describe the relationship among word alignments, phrase table, and machine translation performance. In this paper, on one hand, we focus on formulating such a relationship for estimating the size of extracted phrase pairs given one or more word alignment points. On the other hand, a corpus-motivated pruning technique is proposed to prune the default large phrase table. Experiment proves that the deduced formula is feasible, which not only can be used to predict the size of the phrase table, but also can be a valuable reference for investigating the relationship between the translation performance and phrase tables based on different links of word alignment. The corpus-motivated pruning results show that nearly 98% of phrases can be reduced without any significant loss in translation quality.


---

## Body

## 1. Introduction

One of the best performing translation systems in Statistical Machine Translation (SMT) nowadays is the phrase-based model, which takes continual word sequences as translation units [1, 2].The fundamental data structure in phrase-based models is a table of phrase pairs with associated scores which may come from probability distributions. Until now, several methods to extract phrase pairs from a parallel corpus have been proposed, such as using a probabilistic model [3], pattern mining methods [4], matrix factorization [5], heuristic-based method [6–9], MBR-based method [10], and model-based method [11]. However, most commonly, this table is acquired from word alignments [12–15], which exhaustively enumerates all phrases up to a certain length consistent with the alignment [16].When talking about the relationship between machine translation and word alignment or phrase table, researchers seek for better translation performance from at least two independent research efforts. On the one hand, different processes of interfering word alignments were studied for better translation results. Some researchers have shown that translation quality depends on word alignment quality [7, 17]. Another group of researchers hold an opposite point of view: significant decreases AER (alignment error rate) will not always result in significant increases the translation quality [8, 18, 19]. Recently, researchers in [20] made a systematic study and pointed out that alignments can improve the translation performance depending on the SMT systems and the type of corpus used.On the other hand, phrase table pruning techniques were applied for better machine performance without losing the overall quality. Threshold values are considered to reduce the phrase table size, which are usually related toabsolute scores of phrase pairs in the phrase table orrelative scores between the phrase tables sharing their source phrases. Authors in [21, 22] proposed a significant testing in order to select only those phrase pairs which are the more-than-random occurring ones in the training corpus. References [23, 24] exploited the same idea for the hierarchical SMT. References [25, 26] considered usage statistics of phrase pairs from translating sample data, which are based on how often a phrase pair was considered during decoding and how often it was used in the best translation. In [27, 28], the researchers adaptedtriangulation approach to prune the phrase table, which requires additional bilingual corpora. Authors in [10, 29, 30] modified the phrase extraction methods in order to reduce the phrase table size. In [31, 32], they introduced anentropy-based pruning criterion to prune the generated phrase tables.Both studies tried to reduce the spurious results (errors or redundancies) to investigate the affection to the final translation performance based on different empirical statistics. In other words, many existing methods usually employ ad hoc heuristics without theoretical proof. We try to make a study on the relationship among word alignments, phrase table, and translation quality originally from a mathematical perspective proposed in this paper. The equation indicates that it is necessary to improve the quality of word alignment, even if the alignment does not explicitly connect to the translation quality. In particular, by lowering the quality of alignment, the affection to the translation is very minor. In this paper, two extreme cases are that thebest and theworst quality of word alignments are used to illustrate the situation. Experiment results show that the quality of word alignment will affect the translation performance a lot measured by BLEU [33].The contributions of this paper mainly focus on two aspects: (1) formulating the relationships among word alignment, phrase table, and machine translation; the equations indicate that the better quality of the word alignment, the fewer the phrases will be, and the better translation performance both on phrase-level and finer granularity levels; (2) corpus-motivated pruning techniques to prune the default large phrase table, which can remove nearly 85% of all the phrase pairs without hurting the performance of the translation.The rest of the paper is organized as follows. Section2 reviews the related works and background that will be used in this paper. Section 3 describes the relationship details among the word alignment, phrase table, and machine translation from a mathematical perspective. And a corpus-motivated pruning method is introduced here. Section 4 describes the conducted experiments and presents the obtained results. The paper concludes with a summary and discussions of the results.


## 2. Related Works and Background

Our work is based on the dominant method to obtain a phrase table from word alignment, which trained from the EM (Expectation Maximization) algorithm. To extract the phrases from the word alignment, EM algorithm will be utilized to train the bilingual corpus for several iterations, and then phrase pairs that areconsistent with this word alignment will be extracted. Most of the current Phrase-Based SMT systems rely on the GIZA++ implementation of the IBM Models [34] to produce word alignments, running the algorithm in both directions, source to target and target to source. Various heuristics can then be applied to obtain asymmetrized alignment from those two. Most of them, such asgrow-diag-final-and  [8] start from theintersection of the two word alignments and enrich it with alignment points from theunion.Suppose a phrase pair is represented by(
f
~
,
e
~
) consistent with an alignment a, if all words f
1
,
…
,
f
j
,
…
,
f
J in  f
~ that have alignment points in a have these with words e
1
,
…
,
e
i
,
…
,
e
I in e
~ and vice versa. More formal definition of the consistent with the word alignment can be described as follows [35].(
f
~
,
e
~
) consistent with a
⇔
(1)
∀
e
i
∈
e
~
:
(
e
i
,
f
i
)
∈
a
⟹
f
i
∈
f
~
,
∀
f
i
∈
f
~
:
(
e
i
,
f
i
)
∈
A
⟹
e
i
∈
e
~
,
∃
e
i
∈
e
~
,
f
i
∈
f
~
:
(
e
i
,
f
i
)
∈
a
.This algorithm indicates that all the phrases will be extracted if the biphrases(
f
~
,
e
~
) alone with their alignment a
′ satisfy the following two conditions [36]:(i)
e
~ and f
~ are consecutive word subsequences in the target sentence e and source sentence f, respectively, and neither of them is longer than k words;
(ii)
a
′, the alignment between the words of f
~ and e
~ induced by a, contains at least one link.For the relationship between phrase table and machine translation, most researchers talk about the effects based on different sizes of phrase table, which concerns the phrase table pruning techniques. There are mainly three pruning methods:statistical-based,significance testing, andentropy-based methods. For more details, there areabsolute andrelative pruning methods in thestatistical-based method. Theabsolute pruning methods rely only on the statistics of a single phrase pair (
f
~
,
e
~
). They may prune all translations of a source phrase that fall below a threshold according to the count N
(
f
~
,
e
~
) or the probability p
(
e
~
∣
f
~
) of the phrase pair (
f
~
,
e
~
) as shown in (2). Hence, they are independent of other phrases in the phrase table
(2)
N
(
f
~
,
e
~
)
<
τ
c
,
p
(
e
~
∣
f
~
)
<
τ
p
.However, therelative pruning methods consider the full set of target phrases for a specific source phrase f
~. Given a pruning threshold τ
t, a phrase pair (
f
~
,
e
~
) is discarded if
(3)
p
(
e
~
∣
f
~
)
<
τ
t
max
⁡
e
~
⁡
{
p
(
e
~
∣
f
~
)
}
.Both thesignificance testing andentropy-based method are trying to find a threshold τ to reduce the size of the generated phrase table.For theentropy-based approach, in [32], they used conditionalKullback-Leibler divergence [37] to measure the pruned model p
′
(
e
~
∣
f
~
), which is to be as similar as possible to the original model p
(
e
~
∣
f
~
). Then a pruning threshold τ
E can be chosen and phrase pairs with a contribution to the relative entropy below that threshold are pruned if
(4)
p
(
e
~
∣
f
~
)
[
log
⁡
⁡
p
(
e
~
∣
f
~
)
-
log
⁡
⁡
p
′
(
e
~
∣
f
~
)
]
<
τ
E
.For thesignificance testing pruning approach, it heavily depends on a P-value. The value is calculated from two by twocontingency tables, C
T
(
f
~
,
e
~
), as shown in Table 1, which can be used to represent the relationship between f
~ and e
~, where the N
(
f
~
,
e
~
) is defined as the number of parallel sentences that contain one or more occurrences of f
~ on the source side and e
~ on the target side; N
(
f
~
) is the number of parallel sentences that contain one or more occurrences of f
~ on the source side. N
(
e
~
) is the number of parallel sentences that contain one or more occurrences of e
~ on the target side; and N is the number of parallel sentences.Table 1
Contingency table.
e
-
e
-
′
f
-
N
(
f
-
,
e
-
)
N
(
f
-
)
-
N
(
f
-
,
e
-
)
N
(
f
-
)
f
-
′
N
(
e
-
)
-
N
(
f
-
,
e
-
)
N
-
N
(
f
-
)
-
N
(
e
-
)
-
N
(
f
-
,
e
-
)
N
-
N
(
f
-
)
N
(
e
-
)
N
-
N
(
e
-
)
NFollowingFisher’s exact test, the probability of the contingency table via the hyper geometric distribution can be calculated:
(5)
p
h
(
k
)
=
(
N
(
f
~
)
N
(
f
~
,
e
~
)
)
(
N
-
N
(
f
~
)
N
(
e
~
)
-
N
(
f
~
,
e
~
)
)
(
N
N
(
e
~
)
)
.Then theP-value can be then calculated by summing probabilities for tables that have a larger N
(
f
~
,
e
~
):
(6)
P
-value
(
C
T
(
f
~
,
e
~
)
)
=
∑
k
=
N
(
f
~
,
e
~
)
min
⁡
⁡
(
N
(
f
~
)
,
N
(
e
~
)
)
p
h
(
k
)
.A phrase pair will be discarded if theP-value is greater than τ
F as shown in (7)
(7)
P
-value
(
C
T
(
f
~
,
e
~
)
)
=
∑
k
=
N
(
f
~
,
e
~
)
min
⁡
⁡
(
N
(
f
~
)
,
N
(
e
~
)
)
p
h
(
k
)
>
τ
F
.Generally speaking, the goal of theentropy-based method is to remove theredundant phrases, whereas the other approaches are to try to remove thelow-quality orunreliable phrases.The knowledge introduced above will be used during our discussions on the relationships among word alignment, phase table, and machine translation. More details will be shown in Section3.


## 3. Word Alignment & Phrase Table & Machine Translation

In this section, we can see from a theoretical aspect that the quality of the underlying word alignments has a strong influence both on performances of phrases table and phrase-based SMT system.


### 3.1. Word Alignment & Phrase Table

As introduced in the previous section, there are some direct relationships between phrase table and word alignments. In this part, the relationship between the word alignments and extracted phrases is formulated to estimate the size of the target phrase table. Two different word alignment cases are considered for the relations. Firstly, the phrases are extracted from thefull word alignment links of parallel sentences, which are the best word alignments. Secondly, phrases based on asingle link of word alignment will be made an investigation, which can be treated as the worst alignment information.


#### 3.1.1. Phrases Extraction from Full Word Alignment

Suppose a source sentencef
1
J
=
f
1
f
2
⋯
f
J will be translated into a target sentence e
1
I
=
e
1
e
2
⋯
e
I, and only one target word is allowed to align to one or multiple source words. Where I and J are the length of the target and source sentences, respectively; i and j are the positions of words in the target and source sentences.If each target worde
i has at least one alignment link against the word in source text, named asfull word alignment, fewest phrase pairs can be extracted.For the first case, considering the alignment points in Figure1, each word e
i in the target sentence has at least one alignment point, and there is nocrossing word alignment, which means words are monotonically aligned. Starting with the first word e
1 in the target sentence, the phrase pairs with possible extent can be extracted, for example, (
e
1
∣
f
1
)
,
(
e
1
e
2
∣
f
1
f
2
f
3
)
,
(
e
1
e
2
⋯
e
i
∣
f
1
f
2
f
3
⋯
f
j
)
,
(
e
1
e
2
⋯
e
i
⋯
e
I
∣
f
1
f
2
f
3
⋯
f
j
⋯
f
J
), and so forth, where the total number of I phrase pairs can be obtained. Starting with the second word e
2 in the target sentence, I
-
1 phrase pairs can be extracted, for example, (
e
2
∣
f
2
f
3
)
,
(
e
2
⋯
e
i
∣
f
2
f
3
⋯
f
j
)
,
(
e
2
⋯
e
i
⋯
e
I
∣
f
2
f
3
⋯
f
j
⋯
f
J
), and so on. Thus, the total number of phrase pairs that extracted from the fully aligned sentences can be defined as
(8)
I
+
(
I
-
1
)
+
⋯
+
1
=
I
(
I
+
1
)
2
.Figure 1
Full word alignments.Actually, the previous alignment type cannot deal with the word alignment that contains thecross-alignment, as shown in Figure 2, where the fourth and the fifth Chinese words are cross-aligned with words in source sentence. According to (8), there should be 21 possible phrase pairs. However, only 18 phrases are generated by the conventional phrase extraction algorithm.Figure 2
An example of nonmonotonic alignments where alignment links are crossing between parallel sentences.The general form of above alignments is illustrated in Figure3, where the cross-alignments take place between the neighboring words e
i
begin and e
i
end; that is, i
end
=
i
begin
+
1. Any phrase pairs that fall between the bounds of cross-aligned words cannot be extracted in line with (8). That is, (
i
begin
-
1
)
+
(
I
-
i
end
) phrases should be excluded:
(9)
N
ca
=
(
i
begin
-
1
)
+
(
I
-
i
end
)
.Figure 3
Alignments with a cross link of neighboring words.So if we define the reduced phrases asN
ca (number of cross-alignments), a more practical equation can be revised as
(10)
N
min
⁡
=
I
(
I
+
1
)
2
-
N
ca
.If there is more than one cross-alignment as illustrated in Figure3, the total number of extracted phrases can be generalized as
(11)
N
min
⁡
=
I
(
I
+
1
)
2
-
∑
k
=
1
m
[
(
i
begin
k
-
1
)
+
(
I
-
i
end
k
)
]
.Reduced phrase pairs are determined by the cross-alignment point,i
begin and i
end. i
begin
k represents the start position and i
end
k is the last position of the kth pair words (bounded by the crossing links), and m is the total number of cross-alignments.Figure3 illustrates the situation that there is not any word between the crossing dependencies. However, in reality, there will be any words in between the cross words, as illustrated in Figure 4.Figure 4
Alignments with a cross link involving distant words.For the third case, words betweene
i
begin and e
i
end may have similar alignment situation as that illustrated in (9). Thus, the following equation can be derived to calculate, N
r, the exact number of phrase pairs that cannot be generated. Consider
(12)
N
r
=
∑
k
=
1
m
∑
α
=
0
,
β
=
0
i
end
k
-
i
end
k
-
1
[
(
i
begin
k
+
α
-
1
)
+
(
I
-
i
end
k
+
β
)
]
,
where α indicates the shift word position after the first cross word i
begin
k and β indicates the word position before the end cross word i
end
k. And α
,
β will not be greater than the number of words between the first and the end cross word.Finally, the number of phrase pairs that can be extracted from thefull word alignments measured in thetarget side can be described by
(13)
N
min-
t
=
I
(
I
+
1
)
2
-
N
r
.The equation shows that the size of the phrase table is decided by the target length of the given sentence if the word alignment is the full word alignment, that is, the best and ideal quality word alignment. It is proven that the bidirectional training approach for word alignment can improve the quality of word alignment [8]. If the alignment is deduced from another direction (source side), similarly, the extracted phrases from source side can be represented by
(14)
N
min-
s
=
J
(
J
+
1
)
2
-
N
r
.Equations (13) and (14) show that the number of phrases heavily affected by the length of source and target sentences. Given the best word alignment, if the length in the source sentence equals the target side (
I
=
J
), the phrases will be the minimal numbers (
N
min-
s
or
N
min-
t
). If not equal, the extracted phrases will be larger than this minimal value (
N
min-
s
and
N
min-
t
) afterintersection andunion operations during alignment process.


#### 3.1.2. Phrases Extraction from Worst Alignment

Suppose, only one wordf
j in the source sentence is aligned to a target word e
i as shown in Figure 5. Note that unaligned words near the word f
j may lead to multiple possibilities, each proceeding and following words next to it can form a part of the phrase, and so does the neighboring words of e
i in target sentence. In other words, if we know the different extracted situations in each source and target sentence, and then total counts of phrase pairs can be derived by the product of the two numbers. Algorithm 1 describes the different phrases extraction scenarios according to different positions in the source sentence.Algorithm 1:Phrase extraction based on the only one alignment point: e
i
↔
f
j.
Start frome
1:
N
phrases
=
I
-
i
+
1;
Start frome
2:
N
phrases
=
I
-
i
+
1;
Similarly∀
i
∈
(
i
=
i
,
…
,
I
) in the target side:
N
phrases
=
I
-
i
+
1;Figure 5
Sentences with single alignment link.Obviously, there are totali words that can start with (
e
1
,
e
2
,
e
3
,
…
,
e
i
). Now, in target sentence consisting of odd/even words, the phrase pairs f
(
i
) in different position are
(15)
f
(
i
)
=
i
(
I
-
i
+
1
)
=
i
(
I
-
i
)
+
i
.The phrasesg
(
j
) in the source side can be calculated in a similar way:
(16)
g
(
j
)
=
j
(
J
-
j
+
1
)
=
j
(
J
-
j
)
+
j
.Based on (15) and (16), the total number of phrase pairs N
max
⁡ is given by:
(17)
N
max
⁡
=
[
i
(
I
-
i
)
+
i
]
[
j
(
J
-
j
)
+
j
]
,
where, 0
≤
i
≤
I
-
1 and 0
≤
j
≤
J
-
1.Obviously, (15) and (16) accord withsymmetric distribution, and the maximal value will be achieved in the middle position. Given a sentence consisting of L words, a formal description to the middle position in the sentence can be presented by
(18)
word
mid
{
1
+
L
odd
2
L
even
2
or
(
L
even
2
+
1
)
.We can see that it gives (17) the maximal value in the middle position in a given sentence; that is, the nearer to the middle word, the more phrase pairs can be produced. Take the Figure 2 as an example, there are 18 phrases based on the full word alignments, while the phrases will be 240 when only the fifth word (do) in the source sentence aligns to the third word (做zuo) in the target side. From the view of size of phrase table, the calculation value from (17) is much larger than that from (13). That proves that the better quality of the word alignment, the fewer phrases will be.Note that there will be some share phrases extracted from thefull word alignment and onlysingle word alignment, which leads to the phenomenon that there are still some translation abilities even with only one alignment point under the existing phrase extraction algorithm. For instance, phrase pairs (
e
1
e
2
⋯
e
i
∣
f
1
f
2
f
3
⋯
f
j
)
,
(
e
2
⋯
e
i
∣
f
2
f
3
⋯
f
j
)
,
…
,
(
e
i
∣
f
j
) are the share ones, when given a phrase such as f
1
f
2
f
3
⋯
f
j, both the phrase tables generated from both alignment types can possibly translate it right to e
1
e
2
⋯
e
i.


### 3.2. Phrase Table & Machine Translation

Nowadays, the key step of the process of phrase-based machine translation (SMT) involves inferring a large table of phrase pairs that are translations of each other from a large corpus of aligned sentences. The set of all phrase pairs, together with estimates of conditional probabilities and other useful features, is called Phrase Table (PT), which is applied during the decoding process [29].Nevertheless, phrases in the PT are very dependent from the system that uses them. Some phrases might be present in the PT but never be used in translations because they are either ranked too low or erroneous translations, for example. In other words, there are too many redundant phrases in the PT. Such situation leads many researches to propose different techniques to reduce the size of the phrase table. This includes the methods as introduced in Section2. These works can be treated as the research on the relationship between phrase table and machine translation.All the works presented in Section2 show that the translation results can be achieved from smaller phrase pairs, with several times increase in translation speed with little or no loss in translation accuracy. As reported by [32],count-based andsignificance-based pruning techniques can result in larger savings between 70% and 90%, while theentropy-basedpruning approach can reduce consistently the entries between 85% to 95% of the phrase table. In [29], they even pointed out that the pruning rate can reach to 98% using abilingual segmentation method with finite state transducers. More details about the pruning rates and related translation qualities (measured by BLEU [33]) are shown in Table 2, where the BLEU column is to record the maximal decrease (−) rate from the 100% size of phrase table to the maximal pruning rate of the phrase table.Table 2
Pruned phrase table and translation quality.
Pruning methods
Languages
Pruning rates
BLEU (Δ)
Count/significant
fr-en
64.6%~85.9%
−0.1
es-en
67.9%~88.1%
de-en
62.7%~84.1%
Entropy
fr-en
85%~95%
−1.0
es-en
85%~95%
de-en
85%~95%
Bilingual-segment
fr-en
—
−1.2
es-en
98%
de-en
94%The pruning rates presented above are counted from an empirical or experiment result. We can also estimate the pruning rate from a theoretical aspect. In practice, we also notice that the phrases extracted from the middle word alignment point include most of the phrases that are extracted from the full word alignment. All the phrases excluding the ones extracted from the full word alignment can be removed. In other words, a rough pruning rate can be calculated from the ration of phrases extracted from best alignment (N
min
⁡) and worst alignment (N
max
⁡):
(19)
R
pruned
=
1
-
N
min-
t
N
max
⁡
.If we want to quickly estimate how many percentage of phrases can be pruned in a given corpus, the average statistics of the given corpus can be used as in (20). This equation shows that the pruning rate is not only decided by the sentence length in a parallel corpus but also affected by the alignment position. Consider
(20)
R
pruned
=
1
-
I
average
(
I
average
+
1
)
/
2
[
i
(
I
average
-
i
)
+
i
]
[
j
(
J
average
-
j
)
+
j
]
.In reality, the numerator trends to bigger and the denominator will be smaller, so the pruning rate will be smaller than the calculation value. When the alignment position is in the middle position (middle alignment), there will get the maximal pruning rates as shown in (21). Based on the equation, we can estimate the pruning rate range based on different word alignment position in European corpus [46]. Table 3 shows the statistics of the WMT 2006 and Table 4 compares different pruning rates reported in researchers’ paper [22, 32] and the calculation ranges based on (20). From which we can see that the calculation result is very close to the experiment results presented in [32]. The authors concluded their findings that “the novel entropy-based pruning often achieves the same Bleu score with only half the number of phrases”. A very bold assumption is that most phrases (at least half) can be removed from the original extracted phrases. Consider
(21)
R
max
⁡
=
1
-
I
average
(
I
average
+
1
)
2
×
(
[
i
mid
(
I
average
-
i
mid
)
+
i
mid
]
×
[
j
mid
(
J
average
-
j
mid
)
+
j
mid
]
)
-
1
.Table 3
Training data statistics: WMT 2006.
Language pairs
Sentences
Ave. source len.
Ave. target len.
fr-en
688,031
22.67
20.07
es-en
730,740
21.52
20.83
de-en
751,088
20.31
21.37Table 4
Comparison between theoretical estimation results and other pruning techniques results.
Language pairs
j
mid
i
mid
R
pruned
fr-en
12.34
11.04
53.5%~98.6%
es-en
11.26
11.42
49.3%~98.4%
de-en
11.16
11.19
44.9%~98.3%We have seen that the phrase table pruning rate is strongly affected by the length and word positions in the source and target sentences. As reflected in the pruning equation (20), the phrase table might be more accurately pruned based on some features (e.g., phrase length, phrase cooccurrence) in the bilingual and monolingual corpus. The researchers in [27] reduced the phrase table based on thesignificance testing of phrase pair cooccurrence inbilingual corpus, while He et al. [38, 39] pruned the phrase pairs in terms of phrase frequency in the source side usingkey phrases extracted from amonolingual corpus. We want to make full use of the advantages of the two approaches: thekey phrases can be used to check whether the extracted phrases are often used in practice and thesignificant testing can be used to measure the quality of the extracted phrase pairs. Our methods want to consider the features both for the source and target phrase.The basic metrics for phrases that are often used in practice is the frequency that a phrase appears in a monolingual corpus. The more frequent a phrase appears in a corpus, the greater possibility the phrase may be used. However, longer phrase pairs will be removed in this way because of the fact that those phrases seem to appear rarely in a monolingual corpus.TheC-value is a measurement of automatic term recognition which can be used to solve this problem as described in [40]. The method not only fully considers the frequency information, such as frequencies of a phrase and a subphrase appearing in longer phrases, but also is an efficient algorithm.In this algorithm (as shown in Algorithm2), 4 factors (L, F, S, N) can be used to determine if a phrase p is a key phrase [38]:(i)
L
(
p
), the length of p;
(ii)
F
(
p
), the frequency that p appears in a corpus;
(iii)
S
(
p
), the frequency that p appears as a substring in other longer phrases;
(iv)
N
(
p
), the number of phrases that contain p as a substring.Algorithm 2:Key phrase extraction from monolingual corpus.
Input: Monolingual Corpus
(1) Extracted candidate phrases
(2)for all phrases p in length descending order do
(3)if  N
(
p
)
=
0 then
(4)C
-value
=
(
L
(
p
)
-
1
)
×
F
(
p
)
(5)else
(6)C
-value
=
(
L
(
p
)
-
1
)
×
(
F
(
p
)
-
S
(
p
)
/
N
(
p
)
)
(7)end if
(8)if  C
-value
≥
ε then
(9)   addp to KP
(10)  end if
(11)   for all sub-strings q of p  do
(12)S
(
q
)
=
S
(
q
)
+
F
(
p
)
-
S
(
p
)
(13)N
(
q
)
=
N
(
q
)
+
1
(14)  end for
(15)end for
Output: Key Phrase Table KPGiven a monolingual corpus, key phrases can be extracted efficiently according to Algorithm2. Firstly (line 1), all possible phrases are extracted as candidates of key phrases (e.g., extracted phrase table from Moses [41]). Secondly (line 3 to 7), for each candidate phrase, C-value is computed according to the phrase appearing by itself (line 4) or as a substring of other long phrases (line 6). The C-value is in direct proportion to the phrase length (
L
) and occurrences (
F
,
S
), but in inverse proportion to the number of phrases that contain the phrase as a substring (
N
). This overcomes the limitations of frequency measurement. A phrase is regarded as a key phrase if its C-value is greater than a threshold ε. Finally (line 11 to 14), S
(
q
) and N
(
q
) are updated for each substring q.The algorithm is originally used for pruning the rule table extracted from the hierarchical phrase-based SMT [42]. However, the idea can be also used for phrase-based SMT [1, 41] perfectly. After this filter step, a filtered phrase table called KP will be generated.The phrases in the phrase tableKP are all possibly used phrases in practice. However, there are still some noises in the KP table, for example, the source phrase occurring in source sentences and the target phrase occurring in the target sentences are not well matched; that is, the phrase translation is not good enough. To overcome this case, it is convenient to construct a two by two contingency table that tabulates the sentence pairs where the two types of matches occur and do not occur [21, 22, 43]. The calculation result is also called P-value as introduced in Section 2. A bilingual corpus constraint can be added to filter the noise phrases as presented in Algorithm 3. After this step, a large pruning rate phrase table (called P
_
P
T) will be generated.Algorithm 3:Algorithm for key phrase pruning.
Input: Bilingual Corpus and KP Table from Algorithm 1
(1)for all phrases p
′ in KP do
(2)if  -
log
⁡
(
P
-value
(
p
′
)
)
≤
τ
F then
(3)   addp
′ to P
_PT
(4)end if
(5)end for
Output: Pruned Phrase Table P
_PT


### 3.3. Word Alignment & Machine Translation

Based on the discussion in Sections3.1 and 3.2, we can find that the size of phrase table is heavily affected by the quality of word alignment: the better the word alignment, the smaller size of the phrase table. Besides this, the machine translation performance is not directly decided by the size of the phrase table; at least 50% phrases can be removed without hurting the performance of the machine translation. Experiments show that the quality of phrase translation plays more important role to the final translation quality in practice. Therefore, it is necessary to improve the quality of word alignment under existing phrase extraction algorithm from word alignment.Now, it is a little easier to talk about the relationship between word alignment and machine translation. The translation of sentence is directly derived from the phrase table, while the phrase table is extracted from word alignment. In other words, the quality of word alignment will affect the performance of machine translation through phrase table. That is to say, the word alignment quality will affect the translation performance a lot. However, the works listed in [8, 18, 19] show that there is not always significant affection to the translation result with improved word alignment quality.We do not agree with the conclusion. Firstly, either the training or testing corpus they used in their experiments is limited in a small size or the improvement of the word alignment quality is not significant (AER decrease between 0.1 and 0.2). Secondly, we think it is the existing phrase extraction algorithm that leads to the not obvious result. We have pointed out in the last part of Section3.1 that even the worst alignments are used, the extracted phrase table still have some ability to translate some input phrases. This is because ofthe share phrases extracted from the only one alignment link. The only one word alignment can translate some input phrases or sentences, not mentioning the more word alignment links.We will discuss the situation with different word alignment in next section, where the machine translation affected by the best word alignment and worst word alignment will be fully surveyed. After that we can see that there are at least three advantages to improve the quality of word alignment as follows.(i)
Better alignment will extract fewer phrase pairs and keep a manageable size of phrase table.
(ii)
Better alignment will reduce the decoding time when searching the most possible translation from the phrase table.
(iii)
Better alignment will produce better quality of word or phrase level translation.


## 3.1. Word Alignment & Phrase Table

As introduced in the previous section, there are some direct relationships between phrase table and word alignments. In this part, the relationship between the word alignments and extracted phrases is formulated to estimate the size of the target phrase table. Two different word alignment cases are considered for the relations. Firstly, the phrases are extracted from thefull word alignment links of parallel sentences, which are the best word alignments. Secondly, phrases based on asingle link of word alignment will be made an investigation, which can be treated as the worst alignment information.


### 3.1.1. Phrases Extraction from Full Word Alignment

Suppose a source sentencef
1
J
=
f
1
f
2
⋯
f
J will be translated into a target sentence e
1
I
=
e
1
e
2
⋯
e
I, and only one target word is allowed to align to one or multiple source words. Where I and J are the length of the target and source sentences, respectively; i and j are the positions of words in the target and source sentences.If each target worde
i has at least one alignment link against the word in source text, named asfull word alignment, fewest phrase pairs can be extracted.For the first case, considering the alignment points in Figure1, each word e
i in the target sentence has at least one alignment point, and there is nocrossing word alignment, which means words are monotonically aligned. Starting with the first word e
1 in the target sentence, the phrase pairs with possible extent can be extracted, for example, (
e
1
∣
f
1
)
,
(
e
1
e
2
∣
f
1
f
2
f
3
)
,
(
e
1
e
2
⋯
e
i
∣
f
1
f
2
f
3
⋯
f
j
)
,
(
e
1
e
2
⋯
e
i
⋯
e
I
∣
f
1
f
2
f
3
⋯
f
j
⋯
f
J
), and so forth, where the total number of I phrase pairs can be obtained. Starting with the second word e
2 in the target sentence, I
-
1 phrase pairs can be extracted, for example, (
e
2
∣
f
2
f
3
)
,
(
e
2
⋯
e
i
∣
f
2
f
3
⋯
f
j
)
,
(
e
2
⋯
e
i
⋯
e
I
∣
f
2
f
3
⋯
f
j
⋯
f
J
), and so on. Thus, the total number of phrase pairs that extracted from the fully aligned sentences can be defined as
(8)
I
+
(
I
-
1
)
+
⋯
+
1
=
I
(
I
+
1
)
2
.Figure 1
Full word alignments.Actually, the previous alignment type cannot deal with the word alignment that contains thecross-alignment, as shown in Figure 2, where the fourth and the fifth Chinese words are cross-aligned with words in source sentence. According to (8), there should be 21 possible phrase pairs. However, only 18 phrases are generated by the conventional phrase extraction algorithm.Figure 2
An example of nonmonotonic alignments where alignment links are crossing between parallel sentences.The general form of above alignments is illustrated in Figure3, where the cross-alignments take place between the neighboring words e
i
begin and e
i
end; that is, i
end
=
i
begin
+
1. Any phrase pairs that fall between the bounds of cross-aligned words cannot be extracted in line with (8). That is, (
i
begin
-
1
)
+
(
I
-
i
end
) phrases should be excluded:
(9)
N
ca
=
(
i
begin
-
1
)
+
(
I
-
i
end
)
.Figure 3
Alignments with a cross link of neighboring words.So if we define the reduced phrases asN
ca (number of cross-alignments), a more practical equation can be revised as
(10)
N
min
⁡
=
I
(
I
+
1
)
2
-
N
ca
.If there is more than one cross-alignment as illustrated in Figure3, the total number of extracted phrases can be generalized as
(11)
N
min
⁡
=
I
(
I
+
1
)
2
-
∑
k
=
1
m
[
(
i
begin
k
-
1
)
+
(
I
-
i
end
k
)
]
.Reduced phrase pairs are determined by the cross-alignment point,i
begin and i
end. i
begin
k represents the start position and i
end
k is the last position of the kth pair words (bounded by the crossing links), and m is the total number of cross-alignments.Figure3 illustrates the situation that there is not any word between the crossing dependencies. However, in reality, there will be any words in between the cross words, as illustrated in Figure 4.Figure 4
Alignments with a cross link involving distant words.For the third case, words betweene
i
begin and e
i
end may have similar alignment situation as that illustrated in (9). Thus, the following equation can be derived to calculate, N
r, the exact number of phrase pairs that cannot be generated. Consider
(12)
N
r
=
∑
k
=
1
m
∑
α
=
0
,
β
=
0
i
end
k
-
i
end
k
-
1
[
(
i
begin
k
+
α
-
1
)
+
(
I
-
i
end
k
+
β
)
]
,
where α indicates the shift word position after the first cross word i
begin
k and β indicates the word position before the end cross word i
end
k. And α
,
β will not be greater than the number of words between the first and the end cross word.Finally, the number of phrase pairs that can be extracted from thefull word alignments measured in thetarget side can be described by
(13)
N
min-
t
=
I
(
I
+
1
)
2
-
N
r
.The equation shows that the size of the phrase table is decided by the target length of the given sentence if the word alignment is the full word alignment, that is, the best and ideal quality word alignment. It is proven that the bidirectional training approach for word alignment can improve the quality of word alignment [8]. If the alignment is deduced from another direction (source side), similarly, the extracted phrases from source side can be represented by
(14)
N
min-
s
=
J
(
J
+
1
)
2
-
N
r
.Equations (13) and (14) show that the number of phrases heavily affected by the length of source and target sentences. Given the best word alignment, if the length in the source sentence equals the target side (
I
=
J
), the phrases will be the minimal numbers (
N
min-
s
or
N
min-
t
). If not equal, the extracted phrases will be larger than this minimal value (
N
min-
s
and
N
min-
t
) afterintersection andunion operations during alignment process.


### 3.1.2. Phrases Extraction from Worst Alignment

Suppose, only one wordf
j in the source sentence is aligned to a target word e
i as shown in Figure 5. Note that unaligned words near the word f
j may lead to multiple possibilities, each proceeding and following words next to it can form a part of the phrase, and so does the neighboring words of e
i in target sentence. In other words, if we know the different extracted situations in each source and target sentence, and then total counts of phrase pairs can be derived by the product of the two numbers. Algorithm 1 describes the different phrases extraction scenarios according to different positions in the source sentence.Algorithm 1:Phrase extraction based on the only one alignment point: e
i
↔
f
j.
Start frome
1:
N
phrases
=
I
-
i
+
1;
Start frome
2:
N
phrases
=
I
-
i
+
1;
Similarly∀
i
∈
(
i
=
i
,
…
,
I
) in the target side:
N
phrases
=
I
-
i
+
1;Figure 5
Sentences with single alignment link.Obviously, there are totali words that can start with (
e
1
,
e
2
,
e
3
,
…
,
e
i
). Now, in target sentence consisting of odd/even words, the phrase pairs f
(
i
) in different position are
(15)
f
(
i
)
=
i
(
I
-
i
+
1
)
=
i
(
I
-
i
)
+
i
.The phrasesg
(
j
) in the source side can be calculated in a similar way:
(16)
g
(
j
)
=
j
(
J
-
j
+
1
)
=
j
(
J
-
j
)
+
j
.Based on (15) and (16), the total number of phrase pairs N
max
⁡ is given by:
(17)
N
max
⁡
=
[
i
(
I
-
i
)
+
i
]
[
j
(
J
-
j
)
+
j
]
,
where, 0
≤
i
≤
I
-
1 and 0
≤
j
≤
J
-
1.Obviously, (15) and (16) accord withsymmetric distribution, and the maximal value will be achieved in the middle position. Given a sentence consisting of L words, a formal description to the middle position in the sentence can be presented by
(18)
word
mid
{
1
+
L
odd
2
L
even
2
or
(
L
even
2
+
1
)
.We can see that it gives (17) the maximal value in the middle position in a given sentence; that is, the nearer to the middle word, the more phrase pairs can be produced. Take the Figure 2 as an example, there are 18 phrases based on the full word alignments, while the phrases will be 240 when only the fifth word (do) in the source sentence aligns to the third word (做zuo) in the target side. From the view of size of phrase table, the calculation value from (17) is much larger than that from (13). That proves that the better quality of the word alignment, the fewer phrases will be.Note that there will be some share phrases extracted from thefull word alignment and onlysingle word alignment, which leads to the phenomenon that there are still some translation abilities even with only one alignment point under the existing phrase extraction algorithm. For instance, phrase pairs (
e
1
e
2
⋯
e
i
∣
f
1
f
2
f
3
⋯
f
j
)
,
(
e
2
⋯
e
i
∣
f
2
f
3
⋯
f
j
)
,
…
,
(
e
i
∣
f
j
) are the share ones, when given a phrase such as f
1
f
2
f
3
⋯
f
j, both the phrase tables generated from both alignment types can possibly translate it right to e
1
e
2
⋯
e
i.


## 3.1.1. Phrases Extraction from Full Word Alignment

Suppose a source sentencef
1
J
=
f
1
f
2
⋯
f
J will be translated into a target sentence e
1
I
=
e
1
e
2
⋯
e
I, and only one target word is allowed to align to one or multiple source words. Where I and J are the length of the target and source sentences, respectively; i and j are the positions of words in the target and source sentences.If each target worde
i has at least one alignment link against the word in source text, named asfull word alignment, fewest phrase pairs can be extracted.For the first case, considering the alignment points in Figure1, each word e
i in the target sentence has at least one alignment point, and there is nocrossing word alignment, which means words are monotonically aligned. Starting with the first word e
1 in the target sentence, the phrase pairs with possible extent can be extracted, for example, (
e
1
∣
f
1
)
,
(
e
1
e
2
∣
f
1
f
2
f
3
)
,
(
e
1
e
2
⋯
e
i
∣
f
1
f
2
f
3
⋯
f
j
)
,
(
e
1
e
2
⋯
e
i
⋯
e
I
∣
f
1
f
2
f
3
⋯
f
j
⋯
f
J
), and so forth, where the total number of I phrase pairs can be obtained. Starting with the second word e
2 in the target sentence, I
-
1 phrase pairs can be extracted, for example, (
e
2
∣
f
2
f
3
)
,
(
e
2
⋯
e
i
∣
f
2
f
3
⋯
f
j
)
,
(
e
2
⋯
e
i
⋯
e
I
∣
f
2
f
3
⋯
f
j
⋯
f
J
), and so on. Thus, the total number of phrase pairs that extracted from the fully aligned sentences can be defined as
(8)
I
+
(
I
-
1
)
+
⋯
+
1
=
I
(
I
+
1
)
2
.Figure 1
Full word alignments.Actually, the previous alignment type cannot deal with the word alignment that contains thecross-alignment, as shown in Figure 2, where the fourth and the fifth Chinese words are cross-aligned with words in source sentence. According to (8), there should be 21 possible phrase pairs. However, only 18 phrases are generated by the conventional phrase extraction algorithm.Figure 2
An example of nonmonotonic alignments where alignment links are crossing between parallel sentences.The general form of above alignments is illustrated in Figure3, where the cross-alignments take place between the neighboring words e
i
begin and e
i
end; that is, i
end
=
i
begin
+
1. Any phrase pairs that fall between the bounds of cross-aligned words cannot be extracted in line with (8). That is, (
i
begin
-
1
)
+
(
I
-
i
end
) phrases should be excluded:
(9)
N
ca
=
(
i
begin
-
1
)
+
(
I
-
i
end
)
.Figure 3
Alignments with a cross link of neighboring words.So if we define the reduced phrases asN
ca (number of cross-alignments), a more practical equation can be revised as
(10)
N
min
⁡
=
I
(
I
+
1
)
2
-
N
ca
.If there is more than one cross-alignment as illustrated in Figure3, the total number of extracted phrases can be generalized as
(11)
N
min
⁡
=
I
(
I
+
1
)
2
-
∑
k
=
1
m
[
(
i
begin
k
-
1
)
+
(
I
-
i
end
k
)
]
.Reduced phrase pairs are determined by the cross-alignment point,i
begin and i
end. i
begin
k represents the start position and i
end
k is the last position of the kth pair words (bounded by the crossing links), and m is the total number of cross-alignments.Figure3 illustrates the situation that there is not any word between the crossing dependencies. However, in reality, there will be any words in between the cross words, as illustrated in Figure 4.Figure 4
Alignments with a cross link involving distant words.For the third case, words betweene
i
begin and e
i
end may have similar alignment situation as that illustrated in (9). Thus, the following equation can be derived to calculate, N
r, the exact number of phrase pairs that cannot be generated. Consider
(12)
N
r
=
∑
k
=
1
m
∑
α
=
0
,
β
=
0
i
end
k
-
i
end
k
-
1
[
(
i
begin
k
+
α
-
1
)
+
(
I
-
i
end
k
+
β
)
]
,
where α indicates the shift word position after the first cross word i
begin
k and β indicates the word position before the end cross word i
end
k. And α
,
β will not be greater than the number of words between the first and the end cross word.Finally, the number of phrase pairs that can be extracted from thefull word alignments measured in thetarget side can be described by
(13)
N
min-
t
=
I
(
I
+
1
)
2
-
N
r
.The equation shows that the size of the phrase table is decided by the target length of the given sentence if the word alignment is the full word alignment, that is, the best and ideal quality word alignment. It is proven that the bidirectional training approach for word alignment can improve the quality of word alignment [8]. If the alignment is deduced from another direction (source side), similarly, the extracted phrases from source side can be represented by
(14)
N
min-
s
=
J
(
J
+
1
)
2
-
N
r
.Equations (13) and (14) show that the number of phrases heavily affected by the length of source and target sentences. Given the best word alignment, if the length in the source sentence equals the target side (
I
=
J
), the phrases will be the minimal numbers (
N
min-
s
or
N
min-
t
). If not equal, the extracted phrases will be larger than this minimal value (
N
min-
s
and
N
min-
t
) afterintersection andunion operations during alignment process.


## 3.1.2. Phrases Extraction from Worst Alignment

Suppose, only one wordf
j in the source sentence is aligned to a target word e
i as shown in Figure 5. Note that unaligned words near the word f
j may lead to multiple possibilities, each proceeding and following words next to it can form a part of the phrase, and so does the neighboring words of e
i in target sentence. In other words, if we know the different extracted situations in each source and target sentence, and then total counts of phrase pairs can be derived by the product of the two numbers. Algorithm 1 describes the different phrases extraction scenarios according to different positions in the source sentence.Algorithm 1:Phrase extraction based on the only one alignment point: e
i
↔
f
j.
Start frome
1:
N
phrases
=
I
-
i
+
1;
Start frome
2:
N
phrases
=
I
-
i
+
1;
Similarly∀
i
∈
(
i
=
i
,
…
,
I
) in the target side:
N
phrases
=
I
-
i
+
1;Figure 5
Sentences with single alignment link.Obviously, there are totali words that can start with (
e
1
,
e
2
,
e
3
,
…
,
e
i
). Now, in target sentence consisting of odd/even words, the phrase pairs f
(
i
) in different position are
(15)
f
(
i
)
=
i
(
I
-
i
+
1
)
=
i
(
I
-
i
)
+
i
.The phrasesg
(
j
) in the source side can be calculated in a similar way:
(16)
g
(
j
)
=
j
(
J
-
j
+
1
)
=
j
(
J
-
j
)
+
j
.Based on (15) and (16), the total number of phrase pairs N
max
⁡ is given by:
(17)
N
max
⁡
=
[
i
(
I
-
i
)
+
i
]
[
j
(
J
-
j
)
+
j
]
,
where, 0
≤
i
≤
I
-
1 and 0
≤
j
≤
J
-
1.Obviously, (15) and (16) accord withsymmetric distribution, and the maximal value will be achieved in the middle position. Given a sentence consisting of L words, a formal description to the middle position in the sentence can be presented by
(18)
word
mid
{
1
+
L
odd
2
L
even
2
or
(
L
even
2
+
1
)
.We can see that it gives (17) the maximal value in the middle position in a given sentence; that is, the nearer to the middle word, the more phrase pairs can be produced. Take the Figure 2 as an example, there are 18 phrases based on the full word alignments, while the phrases will be 240 when only the fifth word (do) in the source sentence aligns to the third word (做zuo) in the target side. From the view of size of phrase table, the calculation value from (17) is much larger than that from (13). That proves that the better quality of the word alignment, the fewer phrases will be.Note that there will be some share phrases extracted from thefull word alignment and onlysingle word alignment, which leads to the phenomenon that there are still some translation abilities even with only one alignment point under the existing phrase extraction algorithm. For instance, phrase pairs (
e
1
e
2
⋯
e
i
∣
f
1
f
2
f
3
⋯
f
j
)
,
(
e
2
⋯
e
i
∣
f
2
f
3
⋯
f
j
)
,
…
,
(
e
i
∣
f
j
) are the share ones, when given a phrase such as f
1
f
2
f
3
⋯
f
j, both the phrase tables generated from both alignment types can possibly translate it right to e
1
e
2
⋯
e
i.


## 3.2. Phrase Table & Machine Translation

Nowadays, the key step of the process of phrase-based machine translation (SMT) involves inferring a large table of phrase pairs that are translations of each other from a large corpus of aligned sentences. The set of all phrase pairs, together with estimates of conditional probabilities and other useful features, is called Phrase Table (PT), which is applied during the decoding process [29].Nevertheless, phrases in the PT are very dependent from the system that uses them. Some phrases might be present in the PT but never be used in translations because they are either ranked too low or erroneous translations, for example. In other words, there are too many redundant phrases in the PT. Such situation leads many researches to propose different techniques to reduce the size of the phrase table. This includes the methods as introduced in Section2. These works can be treated as the research on the relationship between phrase table and machine translation.All the works presented in Section2 show that the translation results can be achieved from smaller phrase pairs, with several times increase in translation speed with little or no loss in translation accuracy. As reported by [32],count-based andsignificance-based pruning techniques can result in larger savings between 70% and 90%, while theentropy-basedpruning approach can reduce consistently the entries between 85% to 95% of the phrase table. In [29], they even pointed out that the pruning rate can reach to 98% using abilingual segmentation method with finite state transducers. More details about the pruning rates and related translation qualities (measured by BLEU [33]) are shown in Table 2, where the BLEU column is to record the maximal decrease (−) rate from the 100% size of phrase table to the maximal pruning rate of the phrase table.Table 2
Pruned phrase table and translation quality.
Pruning methods
Languages
Pruning rates
BLEU (Δ)
Count/significant
fr-en
64.6%~85.9%
−0.1
es-en
67.9%~88.1%
de-en
62.7%~84.1%
Entropy
fr-en
85%~95%
−1.0
es-en
85%~95%
de-en
85%~95%
Bilingual-segment
fr-en
—
−1.2
es-en
98%
de-en
94%The pruning rates presented above are counted from an empirical or experiment result. We can also estimate the pruning rate from a theoretical aspect. In practice, we also notice that the phrases extracted from the middle word alignment point include most of the phrases that are extracted from the full word alignment. All the phrases excluding the ones extracted from the full word alignment can be removed. In other words, a rough pruning rate can be calculated from the ration of phrases extracted from best alignment (N
min
⁡) and worst alignment (N
max
⁡):
(19)
R
pruned
=
1
-
N
min-
t
N
max
⁡
.If we want to quickly estimate how many percentage of phrases can be pruned in a given corpus, the average statistics of the given corpus can be used as in (20). This equation shows that the pruning rate is not only decided by the sentence length in a parallel corpus but also affected by the alignment position. Consider
(20)
R
pruned
=
1
-
I
average
(
I
average
+
1
)
/
2
[
i
(
I
average
-
i
)
+
i
]
[
j
(
J
average
-
j
)
+
j
]
.In reality, the numerator trends to bigger and the denominator will be smaller, so the pruning rate will be smaller than the calculation value. When the alignment position is in the middle position (middle alignment), there will get the maximal pruning rates as shown in (21). Based on the equation, we can estimate the pruning rate range based on different word alignment position in European corpus [46]. Table 3 shows the statistics of the WMT 2006 and Table 4 compares different pruning rates reported in researchers’ paper [22, 32] and the calculation ranges based on (20). From which we can see that the calculation result is very close to the experiment results presented in [32]. The authors concluded their findings that “the novel entropy-based pruning often achieves the same Bleu score with only half the number of phrases”. A very bold assumption is that most phrases (at least half) can be removed from the original extracted phrases. Consider
(21)
R
max
⁡
=
1
-
I
average
(
I
average
+
1
)
2
×
(
[
i
mid
(
I
average
-
i
mid
)
+
i
mid
]
×
[
j
mid
(
J
average
-
j
mid
)
+
j
mid
]
)
-
1
.Table 3
Training data statistics: WMT 2006.
Language pairs
Sentences
Ave. source len.
Ave. target len.
fr-en
688,031
22.67
20.07
es-en
730,740
21.52
20.83
de-en
751,088
20.31
21.37Table 4
Comparison between theoretical estimation results and other pruning techniques results.
Language pairs
j
mid
i
mid
R
pruned
fr-en
12.34
11.04
53.5%~98.6%
es-en
11.26
11.42
49.3%~98.4%
de-en
11.16
11.19
44.9%~98.3%We have seen that the phrase table pruning rate is strongly affected by the length and word positions in the source and target sentences. As reflected in the pruning equation (20), the phrase table might be more accurately pruned based on some features (e.g., phrase length, phrase cooccurrence) in the bilingual and monolingual corpus. The researchers in [27] reduced the phrase table based on thesignificance testing of phrase pair cooccurrence inbilingual corpus, while He et al. [38, 39] pruned the phrase pairs in terms of phrase frequency in the source side usingkey phrases extracted from amonolingual corpus. We want to make full use of the advantages of the two approaches: thekey phrases can be used to check whether the extracted phrases are often used in practice and thesignificant testing can be used to measure the quality of the extracted phrase pairs. Our methods want to consider the features both for the source and target phrase.The basic metrics for phrases that are often used in practice is the frequency that a phrase appears in a monolingual corpus. The more frequent a phrase appears in a corpus, the greater possibility the phrase may be used. However, longer phrase pairs will be removed in this way because of the fact that those phrases seem to appear rarely in a monolingual corpus.TheC-value is a measurement of automatic term recognition which can be used to solve this problem as described in [40]. The method not only fully considers the frequency information, such as frequencies of a phrase and a subphrase appearing in longer phrases, but also is an efficient algorithm.In this algorithm (as shown in Algorithm2), 4 factors (L, F, S, N) can be used to determine if a phrase p is a key phrase [38]:(i)
L
(
p
), the length of p;
(ii)
F
(
p
), the frequency that p appears in a corpus;
(iii)
S
(
p
), the frequency that p appears as a substring in other longer phrases;
(iv)
N
(
p
), the number of phrases that contain p as a substring.Algorithm 2:Key phrase extraction from monolingual corpus.
Input: Monolingual Corpus
(1) Extracted candidate phrases
(2)for all phrases p in length descending order do
(3)if  N
(
p
)
=
0 then
(4)C
-value
=
(
L
(
p
)
-
1
)
×
F
(
p
)
(5)else
(6)C
-value
=
(
L
(
p
)
-
1
)
×
(
F
(
p
)
-
S
(
p
)
/
N
(
p
)
)
(7)end if
(8)if  C
-value
≥
ε then
(9)   addp to KP
(10)  end if
(11)   for all sub-strings q of p  do
(12)S
(
q
)
=
S
(
q
)
+
F
(
p
)
-
S
(
p
)
(13)N
(
q
)
=
N
(
q
)
+
1
(14)  end for
(15)end for
Output: Key Phrase Table KPGiven a monolingual corpus, key phrases can be extracted efficiently according to Algorithm2. Firstly (line 1), all possible phrases are extracted as candidates of key phrases (e.g., extracted phrase table from Moses [41]). Secondly (line 3 to 7), for each candidate phrase, C-value is computed according to the phrase appearing by itself (line 4) or as a substring of other long phrases (line 6). The C-value is in direct proportion to the phrase length (
L
) and occurrences (
F
,
S
), but in inverse proportion to the number of phrases that contain the phrase as a substring (
N
). This overcomes the limitations of frequency measurement. A phrase is regarded as a key phrase if its C-value is greater than a threshold ε. Finally (line 11 to 14), S
(
q
) and N
(
q
) are updated for each substring q.The algorithm is originally used for pruning the rule table extracted from the hierarchical phrase-based SMT [42]. However, the idea can be also used for phrase-based SMT [1, 41] perfectly. After this filter step, a filtered phrase table called KP will be generated.The phrases in the phrase tableKP are all possibly used phrases in practice. However, there are still some noises in the KP table, for example, the source phrase occurring in source sentences and the target phrase occurring in the target sentences are not well matched; that is, the phrase translation is not good enough. To overcome this case, it is convenient to construct a two by two contingency table that tabulates the sentence pairs where the two types of matches occur and do not occur [21, 22, 43]. The calculation result is also called P-value as introduced in Section 2. A bilingual corpus constraint can be added to filter the noise phrases as presented in Algorithm 3. After this step, a large pruning rate phrase table (called P
_
P
T) will be generated.Algorithm 3:Algorithm for key phrase pruning.
Input: Bilingual Corpus and KP Table from Algorithm 1
(1)for all phrases p
′ in KP do
(2)if  -
log
⁡
(
P
-value
(
p
′
)
)
≤
τ
F then
(3)   addp
′ to P
_PT
(4)end if
(5)end for
Output: Pruned Phrase Table P
_PT


## 3.3. Word Alignment & Machine Translation

Based on the discussion in Sections3.1 and 3.2, we can find that the size of phrase table is heavily affected by the quality of word alignment: the better the word alignment, the smaller size of the phrase table. Besides this, the machine translation performance is not directly decided by the size of the phrase table; at least 50% phrases can be removed without hurting the performance of the machine translation. Experiments show that the quality of phrase translation plays more important role to the final translation quality in practice. Therefore, it is necessary to improve the quality of word alignment under existing phrase extraction algorithm from word alignment.Now, it is a little easier to talk about the relationship between word alignment and machine translation. The translation of sentence is directly derived from the phrase table, while the phrase table is extracted from word alignment. In other words, the quality of word alignment will affect the performance of machine translation through phrase table. That is to say, the word alignment quality will affect the translation performance a lot. However, the works listed in [8, 18, 19] show that there is not always significant affection to the translation result with improved word alignment quality.We do not agree with the conclusion. Firstly, either the training or testing corpus they used in their experiments is limited in a small size or the improvement of the word alignment quality is not significant (AER decrease between 0.1 and 0.2). Secondly, we think it is the existing phrase extraction algorithm that leads to the not obvious result. We have pointed out in the last part of Section3.1 that even the worst alignments are used, the extracted phrase table still have some ability to translate some input phrases. This is because ofthe share phrases extracted from the only one alignment link. The only one word alignment can translate some input phrases or sentences, not mentioning the more word alignment links.We will discuss the situation with different word alignment in next section, where the machine translation affected by the best word alignment and worst word alignment will be fully surveyed. After that we can see that there are at least three advantages to improve the quality of word alignment as follows.(i)
Better alignment will extract fewer phrase pairs and keep a manageable size of phrase table.
(ii)
Better alignment will reduce the decoding time when searching the most possible translation from the phrase table.
(iii)
Better alignment will produce better quality of word or phrase level translation.


## 4. Experiments and Discussions

In order to evaluate the conclusions drawn in the previous section, some experiments are carried out using Moses toolkit [41], which provides a complete package of the required modules for training and generating the translation of texts.


### 4.1. Experiment Settings

Like other SMT approaches, Moses toolkit requires two models (as shown in Figure6): the Language Model (LM) and the Translation Model (TM). In Moses, LM is usually created by the external toolkits SRILM [44] or IRSTLM [45]. In our experiment, the IRSTLM toolkit is used for the large training corpus. Before training, all the tokenization for languages in European corpus [46] use the integrated scripts in Moses, and the segmentation for Chinese adapts the Stanford Chinese segmenter [47] using CTB (Chinese Tree Bank) standard [48, 49]. The entire language model is trained byfive-gram models.Figure 6
Moses’ main modules and models.The phrases are extracted from the results generated from GIZA++ [8]. The word alignment was trained withten iterations of IBM model 1 and model 4 [34] andsix iterations of the HMM alignment model [50].To extract all the possible phrases to verify (13) and (17), the maximal phrases are limited to 30. This can extract most phrases in terms of word alignments and make us focus on the relations among word alignment, phrase table, and machine translation.In order to better reveal relationships between alignment and phrase table to the translation quality,leftmost,middle, andrightmost word alignment are extracted from the original full alignment in the worst alignment situation (i.e., only one alignment link). Here theleftmost,middle, andrightmost word alignment indicate the word alignment link that aligned to thefirst,middle, andend word in the source language side.


### 4.2. Corpus Information

Three language pairs in WMT 2006 shared translation task are chosen as the training data: French-English (fr-en), German-English (de-en), and Spanish-English (es-en). These three language pairs are used to carry out the experiments for proving the equation deduced in Section3 and relationship between word alignment and machine translation. Table 3 shows the statistics of original corpus [46]. However, the number of phrases extracted from the only one link is too many to be allowed in our server, so the first 100,000 European corpus sentences (statistics shown in Table 5) are chosen to prove the availability of the equations between word alignment and phrase table. Table 6 presents the statistics of 3,064 testing data from WMT 2006 for the same English sentences.Table 5
Statistics of the first 10,000 WMT 2006 corpus.
Languages
Ave. source len.
Ave. en len.
fr-en
22.89
20.15
es-en
21.71
20.94
de-en
20.55
21.42Table 6
Statistics of test data (3,064 sentences).
Languages
Ave. source len.
Ave. en len.
fr-en
32.95
27.81
es-en
29.94
27.81
de-en
26.92
27.81To test our algorithm for pruning the phrase table, a large Chinese-English parallel corpus is brought in. The large corpus consists of two parts: 3,289,497 sentences are from the CWMT 2013 [51] and 4,157,556 sentences are from UM-Corpus [52, 53]. After removing repeat and mismatched sentences in the combined two parts, there are left 7,445,190 sentences and the statistics of the combined parallel corpus are presented in Table 7. Note that the statistics of Chinese sentences are counted both in character level (each Chinese character is treated as one token, CharacterCE  in Table 7) and word level (segmented by Stanford CTB segmenter, presented by CTBCE).Table 7
Statistics of CMWT 2013 + UM-Corpus.
Languages
Tokens
Average length
Vocabularies
English
152,161,233
19.37
1,655,080
CharacterCE
229,110,265
29.16
397,442
CTBCE
123,917,395
15.78
1,331,505The UM-Corpus also contains English, Chinese, and Portuguese monolingual corpora. In this experiment, the English and Chinese corpora are used. There are 35,938,697 English sentences from news domain and more than 70 million Chinese sentences from China portal webpage. The statistics about the two corpora are shown in Table8.Table 8
Statistics of English & Chinese corpora.
Languages
Tokens
Average length
Vocabularies
English
804,584,844
24.64
2,357,374
Chinese
3,007,196,322
33.43
1,533,343The 5000 sentences of test data (named UM-Testing) are designed according to domains in the UM-Corpus. There are 1,500 sentences fornews, 500 sentences forlaws, 500 sentences fornovels, 600 sentences forthesis, 700 sentences foreducation, 600 sentences forscience, and 600 forsubtitle. The statistics of the testing data are shown in Table 9.Table 9
Statistics for EC-Corpus testing data.
Languages
Tokens
Average length
English
118,802
23.76
CharacterCE
153,705
30.74
CTBCE
118,499
23.70


### 4.3. Equation of Word Alignments versus Phrases

The calculation for number of phrases requires the full word alignment links. Full word alignment, in other words, is the best quality of word alignment. It is, obviously, very time-consuming if we manually edit the large word aligned sentences. It is already observed in the past that generative models used for statistical word alignment create alignments of increasing quality as they are exposed to more data [19]. The intuition behind this is simple; as more cooccurrences of source and targets words are observed, the word alignments are better. Following this intuition, if we wish to increase the quality of a word alignment, we allow the alignment process access to extra data which is used only during the alignment process and then removed. If we wish to decrease the quality of a word alignment, we divide the parallel corpus into pieces and align the pieces independently of one another and finally concatenate the results together. In our experiments, we use the entire WMT 2006 corpus as training data firstly, and then the first 100,000 alignments are chosen as the full word alignments.Also, theleftmost,middle, andrightmost word alignment point based on thefull word alignment are obtained based on the results generated by GIZA++.The minimal and maximal sizes of the phrase table extracted from thefull andmiddle word alignment and the differential rates are shown in Table 10. The differential rate is calculated by
(22)
R
diff-min
=
|
N
min
⁡
-
N
moses-min
|
N
min
⁡
,
(23)
R
diff-max
=
|
N
max
⁡
-
N
moses-max
|
N
max
⁡
,
where the N
moses-min and N
moses-max indicate the minimal and maximal phrases extracted from Moses.Table 10
Phrases comparison between Moses extraction and calculation result.
Phrase length
K
=
3
0
Languages
N
moses-min
N
min
⁡
R
diff-min
N
moses-max
N
max
⁡
R
diff-max
fr-en
9,136,283
9,080,307
0.006
1,541,902,790
1,544,021,509
0.001
es-en
10,958,551
10,895,266
0.006
1,401,977,185
1,489,422,170
0.058
de-en
9,219,921
8,929,095
0.033
1,606,176,665
1,686,043,482
0.047From Table10 we can see that the actual number of phrases is close to the calculation result. With the small differential rate, the (13) and (17) can be available to the practical experiments. The difference may come from two reasons: (1) the assumption of full word alignment produced from the GIZA++ may contain too many noises; (2) equations (13) and (17) do not consider repetitions of the extracted phrases.


### 4.4. Phrase Table versus Machine Translation

We have shown that the there is no direct relationship between the size of phrase table and machine translation performance. As reflected in (17) and Table 4, at least half of the phrases can be removed without hurting too much the performance of machine translation. In this part, we want to use the large Chinese-English corpus to test our pruning algorithm based on monolingual and bilingual corpus.According to our experience, different thresholds will generate different size of phrase table and result in different performance of translation. Therefore, one of the key steps is to choose the pruning threshold in Algorithms2 and 3. Firstly, a baseline threshold is calculated from the logarithm of sentences of the given corpus (N), that is, log
⁡
(
N
). For the C-value threshold, the baseline threshold is about 25 (log
⁡
(
3.6
*
10
7
)). For the P-value threshold, the negative logarithm will be chosen. Because the probabilities involved are incredibly tiny, we will work instead with the negative of the natural logs of the probabilities. For example, instead of selecting phrase pairs with a P-value less than exp
⁡
(
-
15
), we will select phrase pairs with a negative-log-P-value greater than 15. The baseline threshold for τ
F is 45 (log
⁡
(
7.4
*
10
6
)). Secondly, the different thresholds will increase or decrease than the baseline threshold. The affection to the phrase table and BLEU scores based on different thresholds is shown in Table 11.Table 11
C-value and P-value threshold effect on the phrase table size and BLEU scores.
Thresholds
UM-Corpus + CWMT 2013
C-value ε
-
log
⁡
(
P
-value
)
τ
F
Phrase table (%)
BLEU (%)
0
0
100
28.13
10
20
83.6
28.09
25
45
52.5
27.98
100
60
29.7
28.11
200
100
14.3
28.27
400
200
2.02
25.78From Table11, we can see that nearly 98% phrases can be discarded with monolingual and bilingual corpora, while the translation quality does not become worse too much (only decrease 2.35). Experiments show that about 85% of the phrase table is reduced and can generate the best translation quality, which not only again proves the similar results as in other researchers [3, 21, 32, 38], but also indicates that most phrases are not needed at all. The best translation can be achieved on the size of about 15% to 30% of the original phrase table. That is to say, only a small fraction of phrases are the essential elements, while major of the extracted phrases are spurious, and in some sense, they are redundancy and should be discarded.


### 4.5. Word Alignment versus Translation Quality

In order to investigate the affection to the translation performance based on different word alignment types and phrase table size, we selected five different types of word alignments to generate the phrase table and then measure the translation quality by BLEU metric: the full word alignment points (A
full), the leftmost word alignment (A
l
most), the sure alignment point (A
sure), the middle word alignment point (A
mid), and the rightmost word alignment point (A
r
most).Clearly, theA
full is the best quality of word alignment and followed by A
sure, which is the only 1-to-1 alignment. The A
l
most, A
mid, and A
r
most are much worse ones, which is only one alignment link. As mentioned previously, all these alignment points are obtained after getting the results generated by GIZA++. The experiment is carried out in WMT 2006 corpus. Based on the different alignment types, the number of phrases extracted and the corresponding translation BLEU are presented in Figure 7 and Table 12 separately.Table 12
Translation performance on different word alignment types.
Languages
BLEU (3,064 sentences)
A
full
A
l
most
A
sure
A
mid
A
r
most
fr-en
24.80
4.48
22.26
9.96
2.48
es-en
30.76
3.12
28.24
11.28
2.32
de-en
21.66
2.30
19.28
9.76
2.94Number of phrases extracted from different word alignment points and their BLEU.
(a)
(b)
(c)
(d)
(e)
(f)The histograms show that there is not any direct proportion relationship between the translation performance and the number of extracted phrases. The numbers in Figure7 show that German-English language pairs can generate the most phrases, while the translation quality is not the best. Although the fewest phrases produced from the Spanish-English language pairs, the best translation performance can be obtained. Explained by (17), more phrases usually lead to worse word alignment quality or it can be said that there are too many unaligned words in the produced alignment results. The results in Figure 7 and Table 12 show that (1) the full word alignment will contribute most to the translation performance and there will not be too much decrease when only the sure alignment is provided; (2) however, thefirst andlast word alignment will not produce too high translation quality; (3) although the middle position word alignment can extract the most phrases, the quality of the translation is not the best and it seems that middle word alignment can contribute more to the finally translation.In fact, the translation from the only one link word alignment should be higher. After all, the default full word alignments have too many noises, which trained from a large training corpus without manual edit.


## 4.1. Experiment Settings

Like other SMT approaches, Moses toolkit requires two models (as shown in Figure6): the Language Model (LM) and the Translation Model (TM). In Moses, LM is usually created by the external toolkits SRILM [44] or IRSTLM [45]. In our experiment, the IRSTLM toolkit is used for the large training corpus. Before training, all the tokenization for languages in European corpus [46] use the integrated scripts in Moses, and the segmentation for Chinese adapts the Stanford Chinese segmenter [47] using CTB (Chinese Tree Bank) standard [48, 49]. The entire language model is trained byfive-gram models.Figure 6
Moses’ main modules and models.The phrases are extracted from the results generated from GIZA++ [8]. The word alignment was trained withten iterations of IBM model 1 and model 4 [34] andsix iterations of the HMM alignment model [50].To extract all the possible phrases to verify (13) and (17), the maximal phrases are limited to 30. This can extract most phrases in terms of word alignments and make us focus on the relations among word alignment, phrase table, and machine translation.In order to better reveal relationships between alignment and phrase table to the translation quality,leftmost,middle, andrightmost word alignment are extracted from the original full alignment in the worst alignment situation (i.e., only one alignment link). Here theleftmost,middle, andrightmost word alignment indicate the word alignment link that aligned to thefirst,middle, andend word in the source language side.


## 4.2. Corpus Information

Three language pairs in WMT 2006 shared translation task are chosen as the training data: French-English (fr-en), German-English (de-en), and Spanish-English (es-en). These three language pairs are used to carry out the experiments for proving the equation deduced in Section3 and relationship between word alignment and machine translation. Table 3 shows the statistics of original corpus [46]. However, the number of phrases extracted from the only one link is too many to be allowed in our server, so the first 100,000 European corpus sentences (statistics shown in Table 5) are chosen to prove the availability of the equations between word alignment and phrase table. Table 6 presents the statistics of 3,064 testing data from WMT 2006 for the same English sentences.Table 5
Statistics of the first 10,000 WMT 2006 corpus.
Languages
Ave. source len.
Ave. en len.
fr-en
22.89
20.15
es-en
21.71
20.94
de-en
20.55
21.42Table 6
Statistics of test data (3,064 sentences).
Languages
Ave. source len.
Ave. en len.
fr-en
32.95
27.81
es-en
29.94
27.81
de-en
26.92
27.81To test our algorithm for pruning the phrase table, a large Chinese-English parallel corpus is brought in. The large corpus consists of two parts: 3,289,497 sentences are from the CWMT 2013 [51] and 4,157,556 sentences are from UM-Corpus [52, 53]. After removing repeat and mismatched sentences in the combined two parts, there are left 7,445,190 sentences and the statistics of the combined parallel corpus are presented in Table 7. Note that the statistics of Chinese sentences are counted both in character level (each Chinese character is treated as one token, CharacterCE  in Table 7) and word level (segmented by Stanford CTB segmenter, presented by CTBCE).Table 7
Statistics of CMWT 2013 + UM-Corpus.
Languages
Tokens
Average length
Vocabularies
English
152,161,233
19.37
1,655,080
CharacterCE
229,110,265
29.16
397,442
CTBCE
123,917,395
15.78
1,331,505The UM-Corpus also contains English, Chinese, and Portuguese monolingual corpora. In this experiment, the English and Chinese corpora are used. There are 35,938,697 English sentences from news domain and more than 70 million Chinese sentences from China portal webpage. The statistics about the two corpora are shown in Table8.Table 8
Statistics of English & Chinese corpora.
Languages
Tokens
Average length
Vocabularies
English
804,584,844
24.64
2,357,374
Chinese
3,007,196,322
33.43
1,533,343The 5000 sentences of test data (named UM-Testing) are designed according to domains in the UM-Corpus. There are 1,500 sentences fornews, 500 sentences forlaws, 500 sentences fornovels, 600 sentences forthesis, 700 sentences foreducation, 600 sentences forscience, and 600 forsubtitle. The statistics of the testing data are shown in Table 9.Table 9
Statistics for EC-Corpus testing data.
Languages
Tokens
Average length
English
118,802
23.76
CharacterCE
153,705
30.74
CTBCE
118,499
23.70


## 4.3. Equation of Word Alignments versus Phrases

The calculation for number of phrases requires the full word alignment links. Full word alignment, in other words, is the best quality of word alignment. It is, obviously, very time-consuming if we manually edit the large word aligned sentences. It is already observed in the past that generative models used for statistical word alignment create alignments of increasing quality as they are exposed to more data [19]. The intuition behind this is simple; as more cooccurrences of source and targets words are observed, the word alignments are better. Following this intuition, if we wish to increase the quality of a word alignment, we allow the alignment process access to extra data which is used only during the alignment process and then removed. If we wish to decrease the quality of a word alignment, we divide the parallel corpus into pieces and align the pieces independently of one another and finally concatenate the results together. In our experiments, we use the entire WMT 2006 corpus as training data firstly, and then the first 100,000 alignments are chosen as the full word alignments.Also, theleftmost,middle, andrightmost word alignment point based on thefull word alignment are obtained based on the results generated by GIZA++.The minimal and maximal sizes of the phrase table extracted from thefull andmiddle word alignment and the differential rates are shown in Table 10. The differential rate is calculated by
(22)
R
diff-min
=
|
N
min
⁡
-
N
moses-min
|
N
min
⁡
,
(23)
R
diff-max
=
|
N
max
⁡
-
N
moses-max
|
N
max
⁡
,
where the N
moses-min and N
moses-max indicate the minimal and maximal phrases extracted from Moses.Table 10
Phrases comparison between Moses extraction and calculation result.
Phrase length
K
=
3
0
Languages
N
moses-min
N
min
⁡
R
diff-min
N
moses-max
N
max
⁡
R
diff-max
fr-en
9,136,283
9,080,307
0.006
1,541,902,790
1,544,021,509
0.001
es-en
10,958,551
10,895,266
0.006
1,401,977,185
1,489,422,170
0.058
de-en
9,219,921
8,929,095
0.033
1,606,176,665
1,686,043,482
0.047From Table10 we can see that the actual number of phrases is close to the calculation result. With the small differential rate, the (13) and (17) can be available to the practical experiments. The difference may come from two reasons: (1) the assumption of full word alignment produced from the GIZA++ may contain too many noises; (2) equations (13) and (17) do not consider repetitions of the extracted phrases.


## 4.4. Phrase Table versus Machine Translation

We have shown that the there is no direct relationship between the size of phrase table and machine translation performance. As reflected in (17) and Table 4, at least half of the phrases can be removed without hurting too much the performance of machine translation. In this part, we want to use the large Chinese-English corpus to test our pruning algorithm based on monolingual and bilingual corpus.According to our experience, different thresholds will generate different size of phrase table and result in different performance of translation. Therefore, one of the key steps is to choose the pruning threshold in Algorithms2 and 3. Firstly, a baseline threshold is calculated from the logarithm of sentences of the given corpus (N), that is, log
⁡
(
N
). For the C-value threshold, the baseline threshold is about 25 (log
⁡
(
3.6
*
10
7
)). For the P-value threshold, the negative logarithm will be chosen. Because the probabilities involved are incredibly tiny, we will work instead with the negative of the natural logs of the probabilities. For example, instead of selecting phrase pairs with a P-value less than exp
⁡
(
-
15
), we will select phrase pairs with a negative-log-P-value greater than 15. The baseline threshold for τ
F is 45 (log
⁡
(
7.4
*
10
6
)). Secondly, the different thresholds will increase or decrease than the baseline threshold. The affection to the phrase table and BLEU scores based on different thresholds is shown in Table 11.Table 11
C-value and P-value threshold effect on the phrase table size and BLEU scores.
Thresholds
UM-Corpus + CWMT 2013
C-value ε
-
log
⁡
(
P
-value
)
τ
F
Phrase table (%)
BLEU (%)
0
0
100
28.13
10
20
83.6
28.09
25
45
52.5
27.98
100
60
29.7
28.11
200
100
14.3
28.27
400
200
2.02
25.78From Table11, we can see that nearly 98% phrases can be discarded with monolingual and bilingual corpora, while the translation quality does not become worse too much (only decrease 2.35). Experiments show that about 85% of the phrase table is reduced and can generate the best translation quality, which not only again proves the similar results as in other researchers [3, 21, 32, 38], but also indicates that most phrases are not needed at all. The best translation can be achieved on the size of about 15% to 30% of the original phrase table. That is to say, only a small fraction of phrases are the essential elements, while major of the extracted phrases are spurious, and in some sense, they are redundancy and should be discarded.


## 4.5. Word Alignment versus Translation Quality

In order to investigate the affection to the translation performance based on different word alignment types and phrase table size, we selected five different types of word alignments to generate the phrase table and then measure the translation quality by BLEU metric: the full word alignment points (A
full), the leftmost word alignment (A
l
most), the sure alignment point (A
sure), the middle word alignment point (A
mid), and the rightmost word alignment point (A
r
most).Clearly, theA
full is the best quality of word alignment and followed by A
sure, which is the only 1-to-1 alignment. The A
l
most, A
mid, and A
r
most are much worse ones, which is only one alignment link. As mentioned previously, all these alignment points are obtained after getting the results generated by GIZA++. The experiment is carried out in WMT 2006 corpus. Based on the different alignment types, the number of phrases extracted and the corresponding translation BLEU are presented in Figure 7 and Table 12 separately.Table 12
Translation performance on different word alignment types.
Languages
BLEU (3,064 sentences)
A
full
A
l
most
A
sure
A
mid
A
r
most
fr-en
24.80
4.48
22.26
9.96
2.48
es-en
30.76
3.12
28.24
11.28
2.32
de-en
21.66
2.30
19.28
9.76
2.94Number of phrases extracted from different word alignment points and their BLEU.
(a)
(b)
(c)
(d)
(e)
(f)The histograms show that there is not any direct proportion relationship between the translation performance and the number of extracted phrases. The numbers in Figure7 show that German-English language pairs can generate the most phrases, while the translation quality is not the best. Although the fewest phrases produced from the Spanish-English language pairs, the best translation performance can be obtained. Explained by (17), more phrases usually lead to worse word alignment quality or it can be said that there are too many unaligned words in the produced alignment results. The results in Figure 7 and Table 12 show that (1) the full word alignment will contribute most to the translation performance and there will not be too much decrease when only the sure alignment is provided; (2) however, thefirst andlast word alignment will not produce too high translation quality; (3) although the middle position word alignment can extract the most phrases, the quality of the translation is not the best and it seems that middle word alignment can contribute more to the finally translation.In fact, the translation from the only one link word alignment should be higher. After all, the default full word alignments have too many noises, which trained from a large training corpus without manual edit.


## 5. Conclusions

In this paper, some investigations are made about the relationship among word alignment, phrase table, and machine translation. After deducing a formula for estimating the size of the phrase table, a maximal phrase pruning ratio can be calculated based on the average length of the given corpus and word alignment positions. Finally, translation performance based on different word alignment types is compared.Equations (13) and (17) provide a simple way to predict the size of the phrase table in advance based on the generated word alignment points. This is beneficial for evaluating how much hardware resources are required to train the model when the size of the parallel corpus is huge.Experiment results show the affection to the translation performance is significant if the AER decreases or increases too much. There is no direct proportion relationship between the translation performance and the number of extracted phrases. In other words, most of the phrases are not needed at all, only phrases extracted from the full word alignment are enough. It can be seen from our corpus-motivated pruning method that only 15%–30% phrases are needed for the basic translations and most phrases in the phrase table are noises to the final translation.Based on the existing phrase extraction algorithm from word alignment, better word alignment will be very helpful to the final translation. There are at least three advantages with a better quality of word alignment even without the existing phrase extraction algorithm improved as follows.(i)
Better alignment will extract fewer phrase pairs and keep a manageable size of phrase table.
(ii)
Better alignment will reduce the decoding time when searching the most possible translation from the phrase table.
(iii)
Better alignment will produce better quality of word or phrase level translation.The next work we want to focus on is to add the corpus-motivated pruning technique into the translation models; that is, the phrases will be filtered during the training time, not after generating the phrase table.



---

*Source: 438106-2014-04-16.xml*