Long-Distance Hierarchical Structure Transformation Rules
Utilizing Function Words
Chenchen Ding, Takashi Inui, Mikio Yamamoto
Department of Computer Science, University of Tsukuba
1-1-1 Tennodai, Tsukuba, 305-8573, Japan{tei@mibel., inui, myama@}cs.tsukuba.ac.jp

Abstract
In this paper, we propose structure transformation rules
for statistical machine translation which are lexicalized byonly function words. Although such rules can be extracted
from an aligned parallel corpus simply as original phrase
pairs, their structure is hierarchical and thus can be used in ahierarchical translation system. In addition, structure transformation rules can take into account long-distance reordering, allowing for more than two phrases to be moved simultaneously. The rule set is used as a core module in our hierarchical model together with two other modules, namely,a basic reordering module and an optional gap phrase module. Our model is considerably more compact and producesslightly higher BLEU scores than the original hierarchicalphrase-based model in Japanese-English translation on theparallel corpus of the NTCIR-7 patent translation task.

1. Introduction
The task of reordering words and phrases in a source language to match the structure of a target language is one of themost challenging problems in statistical machine translation(SMT). In particular, when there are considerable differences
between the source language and the target language in termsof syntactic structure, such as in the case of Japanese and English, global reordering is necessary but difficult to achieve.

Figure 2: A French-English word alignment table
Figs. 1 and 2 show the respective word alignment tables
for a Japanese-English sentence pair from the NTCIR-7 parallel corpus and a French-English sentence pair from the Europarl corpus. Both tables are generated automatically by theword aligner GIZA++ [1][2] with grow-diag-final-and symmetrization heuristics [3]. It is clear that the aligned words(black cells) lie approximately along the main diagonal of
the table in Fig. 2, which indicates the similarity in word andphrase order between French and English, in contrast to Fig.
1, in which the scattering of aligned words away from themain diagonal reveal drastic differences in word and phrase
order between Japanese and English.

Figure 3: Several reordering patterns

Figure 1: A Japanese-English word alignment table

In phrase-based models, the monotone/swap orientationof a phrase pair with respect to its adjacent cell is modeledwith a lexicalized reordering model [4]. As Fig. 3 (A) shows,when the phrase pair < から , f rom > is extracted from159

the training corpus, it can also be seen that swap orientation
exists between this phrase pair and its adjacent cell. Thus,
this information can be quantified by a lexicalized reorderingmodel and used in decoding. Also, in Fig. 3 (B), the phrase
pair < 私 の , my > maintains the monotone orientation
with respect to its adjacent cell. This approach will fail toextract reordering information in more complex alignment
patterns, such as that in Fig. 3 (C), from which the swap
orientation of the phrase pair < だ , is > cannot be extracted
unless the rule generation algorithm is aware that the pair
< 私 の 本 , my book > is integral [5].
As shown in Fig. 1, local monotone/swap reordering is
insufficient in Japanese-English translation. In this regard,
hierarchical phrase-based models [6] can provide higher performance through SCFG-style hierarchical rules. From thealignment in Fig. 3 (C), Rules (1) and (2) can be extracted,
where Rule (1) indicates that the copula (だ) after a nounphrase on the Japanese side appears before the corresponding
noun phrase on the English side, and Rule (2) can translate
the discontinuous part on the Japanese side directly.

In the following section, we describe the procedure forextraction and estimation of structure transformation rules indetail, and in Section 3 we describe the other two modules
used in our hierarchical model. Furthermore, in Section 4 wecompare the performance of our model with that of the original phrase-based model and the hierarchical phrase-basedmodel by using BLEU [7] as a metric of translation quality on the Japanese-English parallel corpus of the NTCIR-7
patent translation task [8]. Finally, in Section 5 we discuss
the properties of our model on the basis of the experimentation results, and in Section 6 we present the direction of
future work.

X → < X1 だ , is X1 >(1)

2. Structure Transformation Rules

X → < 私 の X1 だ , is my X1 >(2)

Although hierarchical phrase-based models are powerful,they usually become excessively large since the original approach is to extract all possible rules. A common strategy inthis case is to apply several heuristics in order to reduce themodel size. Therefore, the original hierarchical phrases areconstrained to form a 2-SCFG; in other words, there can beat most two nonterminals in a hierarchical phrase pair. However, this is not always sufficient for long-distance reordering.

Figure 4: Structure transformation with multi-nonterminal
As illustrated by the example shown in Fig. 4, inJapanese, the postpositions が, に and を in a sentence ora clause are markers of the subject, indirect object and direct
object, respectively, and this three-tuple structural information cannot be captured by a single 2-SCFG rule.
A shortcoming of the original hierarchical phrase-basedmodel is that by performing indiscriminate extraction, usefulrules are always mixed with ineffective rules, and when using
heuristics to reduce the model size, the ineffective rules are
discarded together with a portion of the useful rules.

In this paper, we propose a method for extracting structure transformation rules. The extracted rule set can capture
the exact structural information, as in Rule (3) from the example in Fig. 4, while remaining rather compact.
X → <X1 が X2 に X3 を X4 ,(3)

X1 X4 X3 f rom X2 >2.1. Rule Extraction
In attempting to extract long-distance reordering rules, indiscriminate extraction, namely, the extraction of rules lexicalized by all the words in the vocabulary of the foreign
language, produces results that are redundant and unable toreveal the true sentence structure. Therefore, we focus ona word set I of the foreign language vocabulary which cansuggest the structure of a sentence (e.g., function words), andextract rules lexicalized only by these words from I, thus obtaining a more precise sentence structure.
Another compelling question is how to determine I automatically. However, this issue lies outside the scope of
this paper, and we limit ourselves to the function word set ofJapanese as obtained with the tagging system of the JapaneseMorphological Analyzer ChaSen [9]. Therefore, I is composed of postpositions, conjunctions, auxiliary verbs andpunctuation marks occurring in Japanese. We attempt to
avoid the utilization of full grammatical information in order to generalize our approach. Such information is taken
into account only in the process of determining I, and in allother cases it is no longer needed for the arguments presented
in this paper.
The rules are extracted from an aligned parallel corpus,
which can be obtained automatically with a word alignersuch as GIZA++ and several symmetrization heuristics. If
a set S is defined as all the possible index pairs corresponding to a sentence pair eI1 ,f1J , such thatS = {(i, j) | 1 ≤ i ≤ I, 1 ≤ j ≤ J}

(4)then a subset A of S can be defined by word alignment of eI1
and f1J .
A = {(i, j) | (i, j) ∈ S, and ei is aligned to fj }

160

(5)

The original hierarchical phrases can be extracted from eI1
and f1J with A.
In our approach, once I has been determined, A can bepartitioned into two subsets R and O as follows.
R = {(i, j) | (i, j) ∈ A, and fj ∈ I}

(6)

O = {(i, j) | (i, j) ∈ A, and fj ∈
/ I}

(7)

It is clear that R ∪ O = A and R ∩ O = ∅. Considering theexample in Fig. 1, in Fig. 5 R corresponds to black cells andO corresponds to gray cells, with I composed of the function
words described above.

Figure 6: Compacting the original alignment table˜˜ẽI1 , f˜1J and a new Ã can be obtained, after which phrase pairs
with nonterminals (i.e., hierarchical phrase pairs), can be extracted in the same manner as ordinary phrase pairs.
Nevertheless, several heuristics are still required, where• At least one nonterminal must exist on both sides ofextracted phrase pairs.
• Aligned words (excluding the nonterminal mark X)
must exist in phrase pairs.
• There is a maximum number of words on one or bothsides.
• Adjacent nonterminals are not allowed on the foreign
language side.

Figure 5: The set of R, O and M
We define P as the set of all phrase pairs which can beextracted from a sentence pair eI1 ,f1J with A, after which a
set Po is extracted as a subset of P composed of those phrase
pairs which do not cover (i, j) ∈ R.
Po = {p | p ∈ P, and ∀(i, j) covered by p :(i, j) ∈ A → (i, j) ∈ O}

2.2. Parameter Estimation(8)

Next, a subset M of Po is derived as follows.
M = {p | p ∈ Po , and ∃(i, j) covered by p :(i, j) is covered by q ∈ Po → q = p}

As there is no limit to the number of nonterminals in a
rule, the only constraint is the limit on the number of words
combined with the constraint that there are no adjacent nonterminals on the foreign language side.

(9)

As a result, M contains only the maximum phrase pairs fromPo . In Fig. 5, the phrase pairs of M are enclosed in doublelined boxes. It should be noted that Po (and thus M) is notalways capable of covering all (i, j) ∈ O. As shown in Fig.
5, the Japanese word 次 is a noun translated together with のas the English word follows (literally next ), and therefore thecell < 次, f ollows > cannot be covered by any p ∈ Po .
Finally, each p ∈ M is compacted to a cell and denotedby an aligned nonterminal pair < X, X >. Therefore, thetable in Fig. 5 is transformed into the table in Fig. 6, where
each double-lined box in Fig. 5 is compacted to a single
black cell and corresponding word sequences from the original sentences on both sides are replaced by the nonterminal
mark X. After the compacting process, a new sentence pair

Regarding the parameters of the rules [10], similarly to theoriginal phrase-based model and the hierarchical phrasebased model,• the phrase translation probabilities for both directions• the lexical translation probabilities for both directions• a constant rule penalty exp (1)• a constant word penalty exp (1)are used in our rule set and the other two modules, which will
be described in the following section.
In contrast to the original hierarchical phrase-basedmodel, our approach does not make use of an initial phrase
pair, and therefore the extracted phrase pairs are simply
counted and the phrase translation probabilities are calculated on the basis of the relative frequency in the same manner as in the phrase-based model. Furthermore, if there ismore than one pattern, the lexical translation probabilities ofa phrase pair adopt the probabilities from the most frequently161

occurring alignment pattern. However, if there is still morethan one pattern with the same highest frequency of occurrence, the highest probabilities of the two sides are considered separately.

3. A Multi-Module ModelIn our hierarchical translation model, the structure transformation rule set is the core module. However, since the structure transformation rules alone cannot construct a complete
translation model, two additional simple modules are also incorporated into the proposed model.
3.1. Phrase Reordering Module
The phrase pair set of the original phrase-based model is usedin our model in the following hierarchical phrase style• X → < ア , A >,where ア is a Japanese phrase and A is an English phrase.
For each original phrase pair, the hierarchical reorderingrules of four patterns (not all of which are necessarily available) are further extracted as follows:• X → < ア X1 , A X1 >• X → < ア X1 , X1 A >• X → < X1 ア , A X1 >• X → < X1 ア , X1 A >This module can be regarded as a transformation of thelexicalized reordering model into hierarchical phrase style.
Watanabe et al. [11] proposed similar rules as part of theirmodel, where all monotone/swap rules share the same parameters with the original phrase pairs. Therefore, the rules
are simply phrase pairs with appended nonterminals and do
not contain quantified information about the reordering. In
contrast, our model extracts the monotone/swap hierarchicalrules of the original phrase pairs and estimates the phrasetranslation probabilities separately. The procedure starts
from a phrase pair and searches the adjacent cells or phrase
pairs. Three approaches are considered for the extraction of
the reordering model (a word-based [4], a phrase-based [5]and a hierarchical phrase-based approach [5]) in order to obtain the reordering information.

(marked with *) are white, therefore Rule (10) can be extracted.
X → < ア X 1 , A X1 >(10)
If only the adjacent cells are considered, as in the word-based
extraction described above, the procedure would fail to extract Rule (10) in Fig. 7 (B), where the right-down cell of
the phrase pair < ア , A > is white, even though there
is a phrase pair at the right-down of < ア , A >. The
phrase-based extraction procedure can eliminate this issue
by searching the adjacent phrase pairs instead of the adjacent cells. Hierarchical phrase-based extraction is essentiallythe same as phrase-based extraction, with the exception thatduring the search, the size of the expected adjacent phrase
pairs is unlimited. Usually, the limitation on the size of adjacent phrase pair during the search is the same as that in
the phrase pair extraction. For example, in Fig. 7 (C), if thelength of the extracted phrases on the foreign language sideis set to less than 3 words, then both phrase-based extraction
and word-based extraction would fail, even though there isa relatively large phrase pair at the right-down of the phrase
pair < ア , A >. Lastly, it becomes unnecessary to checkcells marked with * in phrase-based and hierarchical phrasebased extraction due to the consistency of the adjacent phrase
pair.
Although any of the three extraction approaches can beapplied, we do not use two or all of them simultaneously.
The parameters of this module and the procedure for theirestimation are the same as those described in Section 2.2.
3.2. Gap Phrase Module
Considering that the structure transformation rules mightlack the ability to account for local discontinuous phrase
pairs, we also use a gap phrase module as an optional module in our model. This module is composed of rules about
discontinuous parts on one or both sides.
The following five patterns exist for rules with a single
nonterminal:• X → < ア X1 イ , A X1 >• X → < ア X1 イ , X1 A >• X → < ア X1 , A X1 B >• X → < X1 ア , A X1 B >• X → < ア X1 イ , A X1 B >Figure 7: Reordering rule extraction
In Fig. 7 (A), the right-down cell of the phrase pair
< ア , A > is black, while the right-up and left-down cells

We use these rules containing a single nonterminal toconstruct the module. Since the extraction of the rules follows the same procedure as for the original hierarchicalphrases, initial phrases are necessary.
The count of the extracted phrase pairs becomes a problem in this case. The fractional count from a uniform distribution was obtained for all extracted phrases sharing thesame initial phrase in parallel with a simple incremental integer count. Since both counts resulted in equal performance162

we adopted the simple integer count in our experiment. The
parameters of this module and the procedure for their calculation are as same as those described in Section 2.2.

4. Experiment4.1. Decoding with the Multi-Module Model
Since the multi-module model consists of N-SCFG rules, all
the rules are organized in the hierarchical phrase style, and a
CKY++ decoder as implemented in Moses [12] is used.
When there are no referable rules during the decoding,we use the following glue rules, which are also used in theoriginal hierarchical phrase-based model.
• S →<SX , SX >• S →<X , X >A separate penalty exp (1) is assigned to these rules, andall other rules in the proposed model, even from different
modules, share the same rule penalty exp(1) 1 .
4.2. Corpus and Model Settings
Due to the large size of the original hierarchical phrase-basedmodel, only part of the parallel corpus of NTCIR-7 was usedas training data amounting to 100 000 sentence pairs selected
at random from among the 1.8 million sentence pairs in the
corpus. 1842 sentences pairs were used for MERT [13] as adevelopment set, and 1381 sentence pairs were used as thetest set in accordance with the sets of the NTCIR-7 translation task.
GIZA++ was used to obtain word alignments with thedefault settings of Moses together with the grow-diag-finaland symmetrization heuristics, which can achieve the highest
performance in Japanese-English translation. The rules forthe proposed model and the original models were extracted
from the same aligned corpus.
Regarding the extraction heuristics, Moses was used to
extract the original phrase translation model and hierarchical phrase translation model. In the phrase model, the maxphrase-length option was set to 5 with the msd-bidirectionalfe reordering, and in the hierarchical phrase model we set
MaxSpan to 15, MaxSymbolsSource to 5, and both MinHoleSource and MinHoleTarget to 1. In our model, the structure transformation rule set used an initial word set composedof the function words in Japanese as described in Section 2.1,
with at most five words on the Japanese side and no limitation on the number of words on the English side. For thereordering module, the original phrases were extracted withthe maximum length for the Japanese side set to 5 and no
constraints on the English side below the upper bound of 15.
Also, the heuristics of the gap phrase model were the same
1 In our experiment, assigning different rule penalties to rules of different
modules does not lead to any notable improvement in the translation performance, while it increases the risk of morbidity weights due to unstable
minimum error rate training (MERT).

as those used in the original hierarchical phrase model, withthe exception that the number of nonterminals in the originalmodel was set to be between 0 and 2, while our model contained only the set of rules with a single nonterminal withdiscontinuous parts and an integer count of the phrase pairs.
Finally, a 5-gram language model was built with SRILM[14] by applying the interpolated modified Kneser-Ney
method [15] using the English side of all 1.8 million sentencepairs in the corpus.
4.3. Results

Table 1: BLEU scores for the test set of the original phrasebased model (Ph) with different reordering rules (reo.w(ordbased)/reo.ph(rase-based)/reo.h(ierarchical)) and the hierarchical phrase-based model (Hier)
dl/span
P h( reo.w)
P h reo.ph
P h reo.h
Hier

20
27.34
27.41 ≯ P h
27.00 ≮ P h
28.61 ≫ P h

30
27.38
27.61 ≯ P h
27.76 > P h
28.49 ≫ P hTable 2: BLEU scores for the test set of the proposed modelcomposed of R(eo), the reordering module with different
extraction rules (*.w/*.ph/*.h), and G(ap), the gap phrase
module, and S(tr), the structure transformation rule set
dl/span
Reo.w
Reo.phReo.h
GapR.phGapR.hStrR.phStrR.hSGR.phSGR.h

20
26.96 ≮ P h, ≪ H
27.04 ≮ P h, ≪ H
27.36 ≯ P h, ≪ H
27.44 ≯ P h, ≪ H
28.05 ≫ P h, < H
27.75 ≯ P h, ≪ H
28.47 ≫ P h, ≮ H
28.54 ≫ P h, ≮ H
28.79 ≫ P h, ≯ H

30
26.98 ≮ P h, ≪ H
27.33 ≮ P h, ≪ H
27.37 ≮ P h, ≪ H
27.67 ≯ P h, ≪ H
28.08 ≫ P h, < H
28.01 ≫ P h, < H
28.22 ≫ P h, ≮ H
28.91 ≫ P h, > H
28.73 ≫ P h, ≯ H

In the experiment, both the original models and ourmodel were tested on relatively large reordering settings indecoding, with a distortion limit of 20/30 for the phrasebased model and a span of 20/30 for the hierarchical models.
All models were tuned with MERT by using the distortion
limit for phrase-based models and the span for hierarchicalmodels separately. The translation performance was evaluated with BLEU 2 . Furthermore, we used bootstrap resam2 According to [8], The highest single-reference BLEU (SRB) scoreachieved by any SMT system in J-E intrinsic evaluation in NTCIR-7 is27.20, achieved by the NTT Group, and the SRB score of Moses, which
is produced by the organizers, was 27.14 in 2008.

163

Table 3: a translation example
SourceRef erence
Hier
SGR.h

また 、 同時に 強 誘電 体 キャパシタ １２ から BL ２ へ 電荷 が 移動する 。
at the same time , electric charges transfer from the ferroelectric capacitor 12 to bl2 .
at the same time , bl2 to charge is moved from the ferroelectric capacitor 12 .
at the same time , the charge moves from the ferroelectric capacitor 12 to bl2 .

Figure 8: Derivation of the original 2-SCFG in Hier

pling [16] to examine the statistical significance of the obtained results. In Table 1 and Table 2, ≫ (≪) indicates thatthe model on the left side outperforms (is outperformed by)
the model on the right at the p ≤ 0.01 p-level, > (<) indicates the same for the p ≤ 0.05 p-level, and ≯ (≮) indicatesno statistical significance. The comparison was performedby considering the results for models with the same distortion limit or span.
In Table 1, the results for the phrase translation modelwith word-based estimated reordering (reo.w) are regarded
as a baseline and compared with the results for the samephrase translation model with phrase-based (reo.ph) and hierarchical phrase-based (reo.h) reordering. It can be inferredthat although both models provide a certain level of improvement, the difference from word-based reordering is not always statistically significant. In the last row of Table 1,
the results for the original hierarchical phrase-based model
clearly show that it outperformed the original phrase-basedmodel in our Japanese-English translation experiment.
Table 2 shows the results for our model with some or
all proposed modules. The results for Reo indicate thatthe performance of the basic (reordering) module is thesame as that of the original phrase-based model when using phrase-based (.ph) and hierarchical (.h) reordering, although its performance with word-based (.w) reordering iscomparatively low. Furthermore, the results for GapR and
StrR show an improvement (greater for StrR); in otherFigure 9: Structure transformation in SGR
words, both modules can achieve a statistically significant
improvement in performance in comparison with the originalphrase based-model. Here, only the StrR module reaches
approximately the same level of performance as the original hierarchical phrase-based model without statistical significance. Although the performance of the model with all
modules(SGR) is higher than that of the original hierarchicalphrase-based model, the difference is not always statisticallysignificant, which is likely due to unstable MERT.
Table 3 presents an example of translation performed
with our model and the original hierarchical phrase-basedmodel, and Figs. 8 and 9 show the derivations. In the original
2-SCFG derivation in Fig. 8, there is a rule in the gray box
which swaps the two parts around the Japanese word から(literally from), whereas the Japanese word へ is translated
separately as an ordinary word, even though in this case it
is used together with から to express a complete idea (literally ... from ... to ...). As shown in Fig. 9, in our model,
the three-tuple Japanese pattern X3 から X4 へ X5 has beentransformed as an entity into the pattern X5 from X3 to X4
on the English side. Grammatically, the part of X5 is a verb

164

phrase which usually precedes the preposition phrase in English but always follows the postposition phrase in Japanese.
With the structure transformation rules, several phrases canbe moved simultaneously, which allows for long-distance reordering to be realized in translation.

Figure 10: Highest performance of the original model andour hierarchical model, and their size in millions of rules
Fig. 10 clearly shows the large size of the original hierarchical phrase-based model in comparison with our modelwith different modules. The number of rules in the structure transformation rule set is sufficiently small to allow theset to be omitted, considering the size of the other modules.
However, this would affect the result since there is considerable improvement in performance between the model withthis rule set and that without it.

Other more complex models have also been devised.
In English-Japanese translation in [21], the input sentenceswere divided into clauses, which were translated separately,
and the partial translation results were integrated to obtainthe complete translated sentence. Furthermore, in [22], precise morphological analysis was applied in English-Arabictranslation, leading to improved performance. These models are designed for particular translation tasks, where specific language features are considered. Although not completely excluded, grammatical knowledge is used moderately
in our model in order to ensure the robustness and simplicity.
Therefore, our approach is not specific to Japanese and canbe generalized to any other translation task in which global
reordering is necessary.
There are also several approaches to compaction of largetranslation models. As proposed in [23], a significance test
can be used to prune the rule table, while a method based ona log-likelihood ratio is proposed in [24]. Furthermore, in[25], a second-pass extraction is used for selecting suitablephrases. The fact that our model is smaller is only a natural
result of the compact but powerful structure transformation
rule set, and it is not the product of intentional design. In
fact, the reordering module and the gap phrase module are
extracted indiscriminately and could potentially be pruned
even further.

6. Conclusions and Future Work
5. Discussion
Different approaches have been developed to handle thelong-distance reordering problem. Nearly all of these approaches use grammatical information, either only in training
or both in training and decoding.
In [17], the POS tags of the foreign language side wereused in modeling the reordering information as well as indecoding, which is also employed in a lattice, where the sequence and the context of POS tags were taken into accounttogether with words. Furthermore, in the approach proposedin [18], the monotone/swap rules are extracted by the foreign
language parse tree and therefore a large amount of linguisticknowledge is necessary for the foreign language side. Regarding hierarchical phrase-models, in [19], the dominative
relationship of pairs of function words between source andtarget languages were studied, and thus a derivation with amore appropriate structure was able to achieve a higher score.
The function words used in [19] were simply words occurring with high frequency, which might introduce sensitivity
towards the type of corpus used in the training, and the relationship between more than two words was not modeled. The
approach in [19] can also be applied to obtain word alignments [20]. In contrast, our approach involves a hierarchicalrule set which can capture long-distance reordering patterns
with simple and corpus-independent POS knowledge in theinitial step. In fact, both training and decoding are performedat the lexical level and POS tags are not used anywhere in theprocess.

In this paper, we proposed structure transformation rules thatare lexicalized only on a small word set in order to allow for
the extraction of long-distance reordering hierarchical ruleswith more than two nonterminals. In a Japanese-English
translation experiment, it was found that this rule set canvastly improve the performance of our translation system
while maintaining such a small size that it can even be omitted from the total rule set.
In future work, we plan to apply our model on a larger
corpus, such as NTCIR-8 (3 million sentence pairs). Furthermore, we intend to explore methods for obtaining the initialword set automatically, as well as to compare the abilities ofthe method with manual and automatic extraction of the initial word set. We also aim to develop a method for extracting
the structure transformation rules directly from a parallel corpus under some optimization criteria.

7. References[1]

Brown, P. F., Della Pietra, V. J., Della Pietra, S. A., andMercer, R. L., The mathematics of statistical machinetranslation: parameter estimation. Computational Linguistics, Vol.19, No.2, pp. 263-311, 1993.

[2]

Och, F. J., and Ney, H., A systematic comparison of various statistical alignment models Computational Linguistics, Vol.29, No.1, pp. 19-51, 2003.

[3]

Koehn, P., Och, F. J., and Marcu, D., Statistical phrase165based translation. In Proceedings of HLT-NAACL, pp.
48-54, Edmonton, May-June, 2003.
[4]

[5]

Tillmann, C., A unigram orientation model for statistical machine translation. In Proceedings of HLTNAACL, 2004.
Galley, M., and Manning, C. D., A simple and effective hierarchical phrase reordering model. In Proceedings of the 2008 Conference on Empirical Methods in
Natural Language Processing, pp. 848-856, Honolulu,
October,r 2008.

[6]

Chiang, D., Hierarchical phrase-based translation.
Computational Linguistics, Vol.33, No.2, pp. 201-228,
2007.

[7]

Papineni, K., Roukos, S., Ward, T., and Zhu, W.-J.,
BLEU: a method for automatic evaluation of machinetranslation. In Proceedings of the 40th Annual Meetingon Association for Computational Linguistics, pp. 311318, Philadelphia, July, 2002.

[8]

[9]

Fujii, A., Utiyama, M., Yamamoto, M., and Utsuro, T.,
Overview of the patent translation task at the NTCIR-7
Workshop. In Proceedings of NTCIR-7 Workshop Meeting Tokyo, Japan, December 16-19, 2008.
Matsumoto, Y., Takaoka, K., and Asahara, M., ChaSen
morphological analyzer version 2.4.0 user’s manual.
2007.

[10] Och, F. J., and Ney, H., Discriminative training andmaximum entropy models for statistical machine translation. In Proceedings of the 40th Annual Meeting on
Association for Computational Linguistics, pp. 295302, Philadelphia, July, 2002.
[11] Watanabe, T., Tsukada, H., and Isozaki, H., Left-toright target generation for hierarchical phrase-basedtranslation. In Proceedings of the 21st International
Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pp. 777-784, Sydney, Australia, 2006.
[12] Koehn, P., Moses statistical machine translation systemuser manual and code guide. September, 2011.
[13] Och, F. J., Minimum error rate training in statisticalmachine translation. In Proceedings of the 41st Annual
Meeting of the Association for Computational Linguistics, pp. 160-167, July, 2003.
[14] Stolcke, A., SRILM - an extensible language modeling
toolkit In Proc. Intl. Conf. Spoken Language Processing
Denver, Colorado, September, 2002.
[15] Chen, S. F., and Goodman, J., An empirical study ofsmoothing techniques for language modeling. Technical Report TR-10-98, Computer Science Group, Harvard University.

[16] Koehn, P., Statistical significance tests for machinetranslation evaluation. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language
Processing, pp. 388-395, Barcelona, Spain, 2004.
[17] Rottmann, K., and Vogel, S., Word reordering in statistical machine translation with a POS-based distortion
model. The 11th International Conference on Theoretical and Methodological Issues in Machine Translation(TMI-07), Skövde, Sweden, September 7-9, 2007.
[18] Li, C.-H., Zhang, D., Li, M., Zhou, M., Li, M., andGuan, Y., A probabilistic approach to syntax-based reordering for statistical machine translation. In Proceedings of the 45th Annual Meeting of the Association ofComputational Linguistics, pp. 720-727, Prague, Czech
Republic, June, 2007.
[19] Setiawan, H., Kan, M.-Y., Li, H., and Resnik, P.,
Topological ordering of function words in hierarchical phrase-based translation. In Proceedings of the 47th
Annual Meeting of the ACL and the 4th IJCNLP of the
AFNLP, pp. 324-332, Suntec, Singapore, August 2-7,
2009.
[20] Setiawan, H., Dyer, C., and Resnik, P., Discriminative
word alignment with a function word reordering model.
In Proceedings of the 2010 Conference on Empirical
Methods in Natural Language Processing, pp. 534-544,
MIT, Massachusetts, USA, October 9-11, 2010.
[21] Sudoh, K., Duh, K., Tsukada, H., Hirao, T., and Nagata,M., Divide and translate: improving long distance reordering in statistical machine translation. In Proceedings of the Joint 5th Workshop on Statistical MachineTranslation and MetricsMATR, pp. 418-427, Uppsala,Sweden, July 15-16, 2010.
[22] Badr, I., Zbib, R., and Glass, J., Syntactic phrase
reordering for English-to-Arabic statistical machinetranslation. In Proceedings of the 12th Conference of
the European Chapter of the ACL, pp. 86-93, Athens,
Greece, March 30 - April 3, 2009.
[23] Johnson, H., Martin, J., Foster, G., and Kuhn, R., Improving translation quality by discarding most of thephrasetable. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 967-975, Prague, June, 2007.
[24] Wu, H., and Wang, H., Comparative study of wordalignment heuristics and phrase-based SMT. In Proceedings of the MT Summit XI, 2007.
[25] Zettlemoyer, L., and Moore, R., Selective phrase pairextraction for improved statistical machine translation.
In Proceedings of NAACL HLT 2007, Companion Volume, pp. 209-212, Rochester, New York, April, 2007.

166