A Continuous Space Rule Selection Modelfor Syntax-based Statistical Machine Translation
Jingyi Zhang1,2 , Masao Utiyama1 , Eiichro Sumita1
Graham Neubig2 , Satoshi Nakamura2
1
National Institute of Information and Communications Technology,
3-5Hikaridai, Keihanna Science City, Kyoto 619-0289, Japan
2
Graduate School of Information Science, Nara Institute of Science and Technology,
Takayama, Ikoma, Nara 630-0192, Japan
jingyizhang/mutiyama/eiichiro.sumita@nict.go.jp
neubig/s-nakamura@is.naist.jp
S

AbstractS

VP

One of the major challenges for statistical machine translation (SMT) is to choose
the appropriate translation rules based on
the sentence context. This paper proposes a continuous space rule selection(CSRS) model for syntax-based SMT toperform this context-dependent rule selection. In contrast to existing maximum entropy based rule selection (MERS) models, which use discrete representations ofwords as features, the CSRS model islearned by a feed-forward neural network
and uses real-valued vector representations of words, allowing for better generalization. In addition, we propose amethod to train the rule selection models
only on minimal rules, which are more frequent and have richer training data compared to non-minimal rules. We tested
our model on different translation tasks
and the CSRS model outperformed a baseline without rule selection and the previous MERS model by up to 2.2 and 1.1
points of BLEU score respectively.

1

Introduction

In syntax-based statistical machine translation(SMT), especially tree-to-string (Liu et al., 2006;
Graehl and Knight, 2004) and forest-to-string (Miet al., 2008) SMT, a source tree or forest is used as
input and translated by a series of tree-based translation rules into a target sentence. A tree-basedtranslation rule can perform reordering and translation jointly by projecting a source subtree into atarget string, which can contain both terminals andnonterminals.
One of the difficulties in applying this modelis the ambiguity existing in translation rules: a

NP

VP
NP

PRP VBD

DT NN

NP

NP

PRP VBDDT NN

I caught a thief

I caught acold

我 抓 了 一个 贼

我 得 了 感冒

Rule Extraction
S

S
VP

VP

NP

VBD

NP

NP

VBD

NP

x0

caughtx1

x0caughtx1x0 抓 了 x1

x0 得 了 x1

Figure 1: An ambiguous source subtree with different translations (English-to-Chinese).
source subtree can have different target translations extracted from the parallel corpus as shownin Figure 1. Selecting correct rules during decoding is a major challenge for SMT in general, andsyntax-based models are no exception.
There have been several methods proposed toresolve this ambiguity. The most simple method,used in the first models of tree-to-string translation (Liu et al., 2006), estimated the probability ofa translation rule by relative frequencies. For example, in Figure 1, the rule that occurs more times
in the training data will have a higher score. Later,
Liu et al. (2008) proposed a maximum entropy
based rule selection (MERS, Section 2) model forsyntax-based SMT, which used contextual information for rule selection, such as words surrounding a rule and words covered by nonterminals ina rule. For example, to choose the correct rulefrom the two rules in Figure 1 for decoding a particular input sentence, if the source phrase covered by “x1” is “a thief” and this child phrasehas been seen in the training data, then the MERS
model can use this information to determine thatthe first rule should be applied. However, if thesource phrase covered by “x1” is a slightly different phrase, such as “a gunman”, it will be hard for
the MERS model to select the correct rule, because
it treats “thief” and “gunman” as two different andunrelated words.
In this paper, we propose a continuous space
rule selection (CSRS, Section 3) model, which islearned by a feed-forward neural network and replaces the discrete representations of words usedin the MERS model with real-valued vector representations of words for better generalization. For
example, the CSRS model can use the similarityof word representations for “gunman” and “thief”
to infer that “a gunman” is more similar with “athief” than “a cold”.
In addition, we propose a new method, applicable to both the MERS and CSRS models,to train rule selection models only on minimal
rules. These minimal rules are more frequent andhave richer training data compared to non-minimal
rules, making it possible to further relieve the data
sparsity problem.
In experiments (Section 4), we validate theproposed CSRS model and the minimal ruletraining method on English-to-German, Englishto-French, English-to-Chinese and English-toJapanese translation tasks.

lated as follows,
exp

K
P

P

E 0 ,R0

exp

K
P

.
λ k hk

(E 0 , R0 , F )

k=1

(2)

Here, hk are features used in the translation systemand λk are feature weights. Features used in Liu
et al. (2006)’s model contain a language modeland simple features based on relative frequencies,
which do not consider context information.
One of the most important features used in thismodel is based on the log conditional probabilityof the target
string given the input source subtreelog Pr ẽ|t̃ . This allows the model to determine
which target strings are more likely to be used intranslation. However, as the correct translation of
the rules may depend on context that is not directly included in the rule, this simple contextindependent estimate is inherently inaccurate.
2.2

Maximum Entropy Based Rule Selection

To perform context-dependent rule selection, Liuet al. (2008) proposed the MERS model forsyntax-based SMT. They built a maximum entropy classifier for each ambiguous source subtreet̃, which introduced contextual information C andestimated the conditional probability using a loglinear model as shown below,
exp

K
P


λk hk (ẽ, C)

k=1
K





P

Tree-to-String SMT and MERS

λk hk (E, R, F )k=1

Pr (E, R|F ) ≈Pr ẽ|t̃, C =

2



exp
ẽ0

P

.

(3)

λk hk (ẽ0 , C)

k=1

2.1

Tree-to-String SMT

In tree-to-string SMT (Liu et al., 2006), a parsetree for the source sentence F is transformed intoa target sentence E using translation rules R. Eachtree-based translation rule r ∈ R translates asource subtree t̃ into a target string ẽ, which cancontain both terminals and nonterminals. During
decoding, the translation system examines different derivations for each source sentence and outputs the one with the highest probability,

The target strings ẽ are treated as different classes
for the classifier.
Supposing that,• r covers source span [fϕ , fϑ ] and target span[eγ , eσ ],• t̃contains
K{Xk |0 ≤ k ≤ K − 1},

nonterminals• Xk covers source span [fϕk , fϑk ] and target
span [eγk , eσk ],(1)

the MERS model used 5 kinds of source-side features as follows,

For a translation E of a source sentence F with
derivation R, the translation probability is calcu-

1. Lexical features: words around a rule (e.g.
fϕ−1 ) and words covered by nonterminals ina rule (e.g. fϕ0 ).

Ê = arg max Pr (E, R|F ) .
E,R

2. Part-of-speech features:part-of-speech(POS) of context words that are used as
lexical features.
3. Span features: span lengths of source phrases
covered by nonterminals in r.
4. Parent features: the parent node of t̃ in theparse tree of the source sentence.
5. Sibling features: the siblings of the root of t̃.
Note that the MERS model does not use features of the source subtree t̃, because the source
subtree t̃ is fixed for each classifier.
The MERS model was integrated into the translation system as two additional features in Equation 2. Supposing that the derivation R contains
M rules r1 , ..., rM with ambiguous source subtrees, then these two MERS features are as follows,
h1 (E, R, F ) =M
P

C(r) = w1 , ..., wξ
log Pr ẽm |t̃m , Cm

m=1

(4)

where t̃m and ẽm are the source subtree and thetarget string contained in rm , and Cm is the context of rm . h1 is the MERS probability feature,and, h2 is a penalty feature counting the numberof predictions made by the MERS model.

3

Our CSRS Approach

3.1

Modeling

The proposed CSRS model differs from the MERS
model in three ways.
1. Instead of learning a single classifier for eachsource subtree t̃, it learns a single classifier
for all rules.
2. Instead of hand-crafted features, it uses afeed-forward neural network to induce features from context words.
3. Instead of one-hot representations, it uses
distributed representations to exploit similarities between words.
First, with regard to training, our CSRS model follows Zhang et al. (2015) in approximating the posterior probability by a binary classifier as follows,Pr ẽ|t̃, C ≈ Pr v = 1|ẽ, t̃, C ,(6)h2 (E, R, F ) = M,where v ∈ {0, 1} is an indicator of whether t̃ istranslated into ẽ. This is in contrast to the MERS
model, which treated the rule selection problem
as a multi-class classification task. If instead we
attempted to estimate output probabilities for all
different ẽ, the cost of estimating the normalization coefficient would be prohibitive, as the number of unique output-side word strings ẽ is large.
There are a number of remedies to this, including noise contrastive estimation (Vaswani et al.,2013), but the binary approximation method has
been reported to have better performance (Zhang
et al., 2015).
To learn this model, we use a feed-forward neural network with structure similar to neural network language models (Vaswani et al., 2013). The
input of the neural rule selection model is a vector
representation for t̃, another vector representationfor ẽ, and a set of ξ vector representations for both
source-side and target-side context words of r:(5)

In our model, C (r) is calculated differently
depending on the number of nonterminals included in the rule. Specifically, Equation 7 defines Cout (r, n) to be context words (n-grams)
around r and Cin (r, n, Xk ) to be boundary words(n-grams) covered by nonterminal Xk in r.1
Cout (r, n)ϕ−1 θ+n γ−1 σ+n= fϕ−n, fθ+1 , eγ−n , eσ+1
Cin (r, n, Xk )= fϕϕkk +n−1 , fθθkk−(n−1) , eγγkk +n−1 , eσσkk −(n−1)(7)
The context words used for a translation rule rwith K nonterminals are shown as below.
K
=0
=1
>1

C (r)
Cout (r, 6)
Cout (r, 4) , Cin (r, 2, X0 )Cout (r, 2) , Cin (r, 2, X0 ) , Cin (r, 2, X1 )We can see that rules with different numbersof nonterminals K use different context words.2
1
Note that when extracting Cout , we use “hsi” and “h/si”
for context words that exceed the length of the sentence;
When extracting Cin , we use “hnoni” for context words thatexceed the length of the nonterminal. Words that occur lessthan twice in the training data are replaced by “hunki”.
2
In most cases, restrictions on extracted rules will ensurethat rules will only contain two nonterminals. However, whenusing minimal rules as described in the next section, morethan two nonterminals are possible, and in these cases, only
contextual information covered by the first two nonterminals
is used in the input. These cases are sufficiently rare, however, that we chose to consider only the first two.

S
NP
PP

r:
PP

NP

IN NP
PP

on x0
NP

在 x0 上DT: area covered by r

JJ

VP

NP
NN IN DTNP

NN IN PRP

ADJPNN

VBZ RBJJ

The blue rug on the floor of your apartment is really cute: area covered by x0 in r铺在你

公寓 地板 上的蓝色 毛毯 很可爱Figure 2: Context word examples. The red words are contained in Cout (r, 4) and the blue words arecontained in Cin (r, 2, X0 ).
For example, if r does not contain nonterminals,
then Cin is not used. Besides, we use more context words surrounding the rule (Cout (r, 6)) for
rules with K = 0 than rules that contain nonterminals (Cout (r, 4) for K = 1 and Cout (r, 2)
for K > 1). This is based on the intuition thatrules with K = 0 can only use the context words
surrounding the rule as information for rule selection, hence this information is more important thanfor other rules. Figure 2 gives an example of context words when applying the rule r to the example
sentence.
Note that we use target-side context because
source-side context is not enough for selecting
correct rules. Since it is not uncommon for one
source sentence to have different correct translations, a translation rule used in one correct derivation may be incorrect for other derivations. In
these cases, target-side context is useful for selecting appropriate translation rules. 3
The vector representations for t̃, ẽ and C are obtained by using a projection matrix to project each
one-hot input into a real-valued embedding vector.
This projection is another key advantage over the
MERS model. Because the CSRS model learns
one unified model for all rules and can share all
training data to learn better vector representationsof words and rules, and the similarities between
vectors can be used to generalize in cases such as
the “thief/gunman” example in the introduction.
3
It is also possible to consider target-side context in aframework like the MERS model, but we show in experiments that a linear model using the same features as the CSRS
model did not improve accuracy.

After calculating the projections, two hidden
layers are used to combine all inputs. Finally, theneural network has two
outputs Pr v = 1|ẽ, t̃, C
and Pr v = 0|ẽ, t̃, C .
To train the CSRS model, we need both positive and negative training examples. Positive examples, ẽ, t̃, C, 1 , can be extracted directly fromthe parallel corpus. For each positive example, we
generate one negative example, ẽ0 , t̃, C, 0 . Here,ẽ0 is randomly generated according to the translation distribution (Zhang et al., 2015),Pr ẽ|t̃ = P

Count ẽ, t̃ẽ0Count ẽ0 , t̃

,

(8)



where, Count ẽ, t̃ is how many times t̃ is translated into ẽ in the parallel corpus.
During translating, following the MERS model,
the CSRS model only calculates probabilities forrules with ambiguous source subtrees. These predictions are converted into two CSRS features forthe translation system similar to the two MERS
features in Equation 4: one is the product of probabilities calculated by the CSRS model and theother one is a penalty feature that stands for how
many rules with ambiguous source subtrees arecontained in one translation.
3.2

Usage of Minimal Rules

Despite the fact that the CSRS model can share information among instances using distributed word
representations, it still poses an extremely sparselearning problem. Specifically, the numbers of
unique subtrees t̃ and strings ẽ are extremely large,

PP
NP
IN

DT

NN

on

the

table

在

桌子

上

extract

Rule1

Rule2

Rule3

Source tree
NN

Target string

table
NP

桌子

DT

NN

the

table
NP

DT

NN

桌子

the
x0
PP

x0

NP
IN

DT

NN

Rule4 on

the
PP

table

在 桌子 上IN NP
在 x0 上

on x0
PP

Rule5

NP
IN

DT

NN

Rule6 onthex0

ory and can be trained faster.
To take advantage of this fact, we train anotherversion of the CSRS model (CSRS-MINI) over
only minimal rules. The probability of a nonminimal rule is then calculated using the product of the probability of minimal rules contained
therein.
Note that for both the standard CSRS andCSRS-MINI models, we use the same baselinetranslation system which can use non-minimaltranslation rules. The CSRS-MINI model will
break translation rules used in translations down
into minimal rules and multiply all probabilities tocalculate the necessary features.

在 x0 上Figure 3: Rules.
and many may only appear a few times in the corpus. To reduce these problems of sparsity, we propose another improvement to the model, specifically through the use of minimal rules.
Minimal rules (Galley et al., 2004) are translation rules that cannot be split into two smaller
rules. For example, in Figure 3, Rule2 is not aminimal rule, since Rule2 can be split into Rule1and Rule3. In the same way, Rule4 and Rule6
are not minimal while Rule1, Rule3 and Rule5 areminimal.
Minimal rules are more frequent than nonminimal rules and have richer training data.
Hence, we can expect that a rule selection modeltrained on minimal rules will suffer less from data
sparsity problems. Besides, without non-minimal
rules, the rule selection model will need less mem-

4

Experiments

4.1

Setting

We evaluated the proposed approach for Englishto-German (ED), English-to-French (EF),English-to-Chinese (EC) and English-to-Japanese(EJ) translation tasks. For the ED and EF tasks,
the translation systems are trained on Europarl
v7 parallel corpus and tested on the WMT 2015translation task.4 The test sets for the WMT 2014translation task were used as development setsin our experiments. For the EC and EJ tasks, weused datasets provided for the patent machinetranslation task at NTCIR-9 (Goto et al., 2011).5
The detailed statistics for training, development
and test sets are given in Table 1. The word
segmentation was done by BaseSeg (Zhao et al.,2006) for Chinese and Mecab6 for Japanese.
For each translation task, we used Travatar(Neubig, 2013) to train a forest-to-string translation system. GIZA++ (Och and Ney, 2003) wasused for word alignment. A 5-gram language
model was trained on the target side of the training corpus using the IRST-LM Toolkit7 with modified Kneser-Ney smoothing. Rule extraction was
4
The WMT tasks provided other training corpora. We
used only the Europarl corpus, because training a large-scale
system on the whole data set requires large amounts of timeand computational resources.
5
Note that NTCIR-9 only contained a Chinese-to-English
translation task. Because we want to test the proposed approach with a similarly accurate parsing model across ourtasks, we used English as the source language in our experiments. In NTCIR-9, the development and test sets were bothprovided for the CE task while only the test set was provided
for the EJ task. Therefore, we used the sentences from the
NTCIR-8 EJ and JE test sets as the development set in our
experiments.
6
http://sourceforge.net/projects/mecab/files/
7
http://hlt.fbk.eu/en/irstlm

TRAIN
ED
DEV
TEST
TRAIN
EF
DEV
TEST
TRAIN
EC
DEV
TEST
TRAIN
EJ
DEV
TEST

#Sents#Words#Vocab#Sents#Words#Sents#Words#Sents#Words#Vocab#Sents#Words#Sents#Words#Sents#Words#Vocab#Sents#Words#Sents#Words#Sents#Words#Vocab#Sents#Words#Sents#WordsSOURCE TARGET
1.90M
52.2M
49.7M
113K
376K
3,003
67.6K
63.0K
2,169
46.8K
44.0K
1.99M
54.4M
60.4M
114K
137K
3,003
71.1K
81.1K
1.5K
27.1K
29.8K
954K
40.4M
37.2M
504K
288K
2K
77.5K
75.4K
2K
58.1K
55.5K
3.14M
104M
118M
273K
150K
2K
66.5K
74.6K
2K
70.6K
78.5K

Table 1: Data sets.
performed using the GHKM algorithm (Galley etal., 2006) and the maximum numbers of nonterminals and terminals contained in one rule were set
to 2 and 10 respectively. Note that when extracting
minimal rules, we release this limit. The decoding
algorithm is the bottom-up forest-to-string decoding algorithm of Mi et al. (2008). For English
parsing, we used Egret8 , which is able to output
packed forests for decoding.
We trained the CSRS models (CSRS and CSRSMINI) on translation rules extracted from thetraining set. Translation rules extracted from thedevelopment set were used as validation data formodel training to avoid over-fitting. For different
training epochs, we resample negative examples
for each positive example to make use of different negative examples. The embedding dimension
was set to be 50 and the number of hidden nodes
was 100. The initial learning rate was set to be 0.1.
The learning rate was halved each time the validation likelihood decreased. The number of epoches
was set to be 20. A model was saved after eachepoch and the model with highest validation likelihood was used in the translation system.
We implemented Liu et al. (2008)’s MERS
model to compare with our approach. The train8

https://code.google.com/archive/p/egret-parser

Base
MERS
CSRS
MERS-MINICSRS-MINI

ED
15.00
15.62
16.15
15.77
16.49

EF
26.76
27.33
28.05
28.13
28.30

EC
29.42
29.75
30.12
30.53
31.63

EJ
37.10
37.76
37.83
38.14
38.32

Table 2: Translation results. The bold numbers
stand for the best systems.
CSRS vs. MERSCSRS-MINI vs. MERS-MINI
MERS-MINI vs. MERSCSRS-MINI vs. CSRS

ED
>>
>>
−
>

EF
>>
−
>>
−

EC
>
>>
>>
>>

EJ
−
−
>>
>>

Table 3: Significance test results. The symbol >>(>) represents a significant difference at the p <0.01 (p < 0.05) level and the symbol - represents
no significant difference at the p < 0.05 level.
ing instances for their model were extracted fromthe training set. Following their work, the iteration
number was set to be 100 and the Gaussian prior
was set to be 1. We also compared the original
MERS model and the MERS model trained only
on minimal rules (MERS-MINI) to test the benefit
of using minimal rules for model training.
The MERS and CSRS models were both used
to calculate features used to rerank unique 1,000best outputs of the baseline system. Tuning is performed to maximize BLEU score using minimum
error rate training (Och, 2003).
4.2

Results

Table 2 shows the translation results and Table 3
shows significance test results using bootstrap resampling (Koehn, 2004): “Base” stands for thebaseline system without any; “MERS”, “CSRS”,“MERS-MINI” and “CSRS-MINI” means the outputs of the baseline system were reranked using
features from the MERS, CSRS, MERS-MINI and
CSRS-MINI models respectively. Generally, the
CSRS model outperformed the MERS model andthe CSRS-MINI model outperformed the MERSMINI model on different translation tasks. In addition, using minimal rules for model training benefitted both the MERS and CSRS models.
Table 4 shows translation examples in the
EC task to demonstrate the reason why our approach improved accuracy. Among all translations, TCSRS−M IN I is basically the same as thereference with only a few paraphrases that do
not alter the meaning of the sentence. In con-

Source
Reference

typical dynamic response rate of an optical gap sensor as described above is approximately 2 khz , or
0.5 milliseconds .
上述(described above) 光学(optical) 间隙(gap) 传感器(sensor) 的 典型(typical) 动态(dynamic) 响应(response) 率(rate) 约(approximately) 为(is) 2KHz 或(or) 为 0.5 毫秒(milliseconds) 。

TBase

典 型(typical) 的 动 态(dynamic) 响 应(response) 速 率(rate)

间隙(gap) 传感器(sensor)

的光学(optical) 如上(above) 描述(described) 的 是(is) 约(approximately) 2 千赫(khz) 兹 ， 或(or)0.5 毫秒(milliseconds) 。
TM ERS典 型(typical) 的 动 态(dynamic) 响 应(response) 率(rate) 光学(optical) 传感器(sensor) ， 如(as)以 上(above) 所 述(described) 间隙(gap) 的 约(approximately) 2 千 赫(khz) ， 或(or) 0.5 毫秒(milliseconds) 。

TCSRS

光学(optical) 传感器(sensor) ， 如(as) 以上(above) 所 述(described) 间隙(gap) 的 典型(typical)
的 动态(dynamic) 响应(response) 速率(rate) 为(is) 约(approximately) 2 千赫(khz) 兹 ， 或(or) 0.5
毫秒(milliseconds) 。

TM ERS−M IN I

典 型(typical) 的 动 态(dynamic) 响 应(response) 率(rate)

间隙(gap) 传感器(sensor)

的光学(optical) 如 上(above) 描 述(described) 的 是(is) 约(approximately) 2 千 赫(khz) 兹 ，或(or) 0.5 毫秒(milliseconds) 。
TCSRS−M IN I

如 上(above) 描 述(described) 的 光学(optical) 间隙(gap) 传感器(sensor) 典 型(typical) 的 动态(dynamic) 响应(response) 速率(rate) 为(is) 约(approximately) 2 千赫(khz) 兹 ， 或(or) 0.5 毫秒(milliseconds) 。

Table 4: Translation examples.
R1 : TM ERS &TCSRS
R2 : TM ERS−M IN I
R3 : TCSRS−M IN I

PP ( IN ( “of” ) NP ( NP ( DT ( “an” ) NP’ ( JJ ( “optical” ) x0:NN ) ) x1:NP’ ) )→ “光学(optical)” x1 x0 “的”PP ( IN ( “of” ) NP ( NP ( DT ( “an” ) NP’ ( JJ ( “optical” ) x0:NP’ ) ) x1:SBAR ) )→ x0 “的” “光学(optical)” x1 “的”NP’ ( JJ ( “optical” ) x0:NP’ ) → “光学(optical)” x0

Table 5: Rules used to translate the source word “optical” in different translations. Shadows (R3 ) standfor ambiguous rules.
trast, TBase , TM ERS , TCSRS and TM ERS−M IN I
all contain apparent mistakes. For example, thesource phrase “optical gap sensor” (covered bygray shadows in Table 4) is wrongly translated in
TBase , TM ERS , TCSRS and TM ERS−M IN I due toincorrect reorderings.
Table 5 shows rules used to translate the source
word “optical” in different translations: R1 isused in TM ERS and TCSRS ; R2 is used in
TM ERS−M IN I ; R3 is used in TCSRS−M IN I . Although the source word “optical” is translated tothe correct translation “光学(optical)” in all translations, R1 , R2 and R3 cause different reorderings
for the source phrase “optical gap sensor”. R3 reorders this source phrase correctly while R1 andR2 cause wrong reorderings for this source phrase.
We can see that R1 is umambiguous, so the
MERS and CSRS models will give probability 1
to R1 , which could make the MERS and CSRS
models prefer TM ERS and TCSRS . This is a typical translation error caused by sparse rules since

the source subtree in R1 does not have other translations in the training corpus.
To compare the MERS-MINI and CSRS-MINI
models, Table 6 shows minimal rules (R2a , R2b ,R3a and R3b ) contained in R2 and R3 . Table 7
shows probabilities of these minimal rules calculated by the MERS-MINI and CSRS-MINI models respectively. We can see that the CSRSMINI model gave higher scores for the correcttranslation rules R3a and R3b than the MERSMINI model, while the MERS-MINI model gavea higher score to the incorrect rule R2b than the
CSRS-MINI model.
Note that R2b and R3b are the same rule,
but the target-side context in TM ERS−M IN I andTCSRS−M IN I is different. The CSRS-MINI
model will give R2b and R3b different scores because the CSRS-MINI model used target-side context. However, the MERS-MINI model only usedsource-side features and gave R2b and R3b thesame score. The fact that the CSRS-MINI model

R2a

R2b

PP ( IN ( “of” ) NP ( NP ( DT ( “an” )NP’ ( x0:JJ x1:NP’ ) ) x2:SBAR ) )→ x1 “的” x0 x2 “的”JJ ( “optical” ) → “光学(optical)”R3aNP’ ( x0:JJ x1:NP’ ) → x0 x1

R3b

JJ ( “optical” ) → “光学(optical)”Table 6: Minimal rules contained in R2 and R3 .
Shadows (R2b , R3a and R3b ) stand for ambiguous
rules.
R2a
R2b
R3a
R3b

MERS-MINI
1
0.5441
0.99430.5441CSRS-MINI
1
0.09632
0.99870.7317

Table 7: Scores of minimal rules.
gave a higher score for R3b than R2b means that
the CSRS-MINI model predicted the target stringin R2b and R3b is a good translation in the context of TCSRS−M IN I but not so good in the context of TM ERS−M IN I . As we can see, the target phrase “如上(above) 描述(described) 的(of)光学(optical) 间隙(gap) 传感器(sensor)” around“光学(optical)” in TCSRS−M IN I is a reasonable
Chinese phrase while the target phrase “间隙(gap)传感器(sensor) 的(of) 光学(optical) 如上(above)
描 述(described) 的(of)” around “光 学(optical)”in TM ERS−M IN I does not make sense. Namely,
the CSRS model trained with target-side context
can perform rule selection considering target sentence fluency, which is the reason why target-side
context can help in the rule selection task.
4.3

Analysis

To analyze the influence of different features, wetrained the MERS model using source-side andtarget-side n-gram lexical features similar to the
CSRS model. When using this feature set, theperformance of the MERS model dropped significantly. This indicates that the syntactic, POS andspan features used in the original MERS model
are important for their model, since these features can generalize better. Purely lexical features
are less effective due to sparsity problems whentraining one maximum entropy based classifier foreach ambiguous source subtree and training data
for each classifier is quite limited. In contrast,
the CSRS model is trained in a continuous spaceand does not split training data, which relieves thesparsity problem of lexical features. As a result,
the CSRS model achieved better performance us-

ing only lexical features compared to the MERS
model. We also tried to use pre-trained word embedding features for the MERS model, but it did
not improve the performance of the MERS model,
which indicates that the log-linear model is notable to benefit from distributed representations aswell as the neural network model.
We also tried reranking with both the CSRS andMERS models added as features, but it did notachieve further improvement compared to only using the CSRS model. This indicates that althoughthese two models use different type of features, theinformation contained in these features are similar.
For example, the POS features used in the MERS
model and the distributed representations used in
the CSRS model are both used for better generalization.
In addition, using both the CSRS and CSRSMINI models did not improve over using only
the CSRS-MINI model in our experiments. There
are two main differences between the CSRS andCSRS-MINI models. First, minimal rules are
more frequent and have more training data thannon-minimal rules, which is why the CSRS-MINI
model is more robust than the CSRS model. Second, non-minimal rules contain more information than minimal rules. For example, in Figure 3, Rule4 contains more information thanRule1, which could be an advantage for rule selection. However, the information contained in Rule4
will be considered as context features for Rule1.
Therefore, this is no longer an advantage for the
CSRS model as long as we use rich enough context features, which could be the reason why using
both the CSRS and CSRS-MINI models cannot
further improve the translation quality compared
to using only the CSRS-MINI model.

5

Related WorkThe rule selection problem for syntax-based SMT
has received much attention. He et al. (2008)
proposed a lexicalized rule selection model to perform context-sensitive rule selection for hierarchical phrase-base translation. Cui et al. (2010) introduced a joint rule selection model for hierarchical phrase-based translation, which also approximated the rule selection problem by a binary classification problem like our approach. However,these two models adopted linear classifiers similar to those used in the MERS model (Liu et al.,2008), which suffers more from the data sparsity

problem compared to the CSRS model.
There are also existing works that exploitedneural networks to learn translation probabilities for translation rules used in the phrase-basedtranslation model. Namely, these methods estimated translation probabilities for phrase pairs extracted from the parallel corpus. Schwenk (2012)
proposed a continuous space translation model,
which calculated the translation probability foreach word in the target phrase and then multiplied the probabilities together as the translation
probability of the phrase pair. Gao et al. (2014)
and Zhang et al. (2014) proposed methods tolearn continuous space phrase representations anduse the similarity between the source and target phrases as translation probabilities for phrase
pairs. All these three methods can only be used forthe phrase-based translation model, not for syntaxbased translation models.
There are also works that used minimal rules formodeling. Vaswani et al. (2011) proposed a rule
Markov model using minimal rules for both training and decoding to achieve a slimmer model, afaster decoder and comparable performance withusing non-minimal rules. Durrani et al. (2013)
proposed a method to model with minimal translation units and decode with phrases for phrasebased SMT to improve translation performances.
Both of these two methods do not use distributed
representations as used in our model for better
generalization.
In addition, neural machine translation (NMT)
has shown promising results recently (Sutskever
et al., 2014; Bahdanau et al., 2014; Luong et al.,2015a; Jean et al., 2015; Luong et al., 2015b).
NMT uses a recurrent neural network to encode
the whole source sentence and then produce thetarget words one by one. These models can betrained on parallel corpora and do not need wordalignments to be learned in advance. There arealso neural translation models that are trained on
word-aligned parallel corpus (Devlin et al., 2014;
Meng et al., 2015; Zhang et al., 2015; Setiawan
et al., 2015), which use the alignment information
to decide which parts of the source sentence are
more important for predicting one particular target
word. All these models are trained on plain source
and target sentences without considering any syntactic information while our neural model learns
rule selection for tree-based translation rules andmakes use of the tree structure of natural language

for better translation. There is also a new syntactic NMT model (Eriguchi et al., 2016), which
extends the original sequence-to-sequence NMT
model with the source-side phrase structure. Although this model takes source-side syntax into
consideration, it still produces target words one
by one as a sequence. In contrast, the tree-basedtranslation rules used in our model can take advantage of the hierarchical structures of both source
and target languages.

6

Conclusion

In this paper, we propose a CSRS model forsyntax-based SMT, which is learned by a feedforward neural network on a continuous space.
Compared with the previous MERS model thatused discrete representations of words as features,
the CSRS model uses real-valued vector representations of words and can exploit similarity information between words for better generalization.
In addition, we propose to use only minimal rules
for rule selection to further relieve the data sparsity problem, since minimal rules are more frequent and have richer training data. In our experiments, the CSRS model outperformed the previous MERS model and the usage of minimal rules
benefitted both CSRS and MERS models on different translation tasks.
For future work, we will explore more sophisticated features for the CSRS model, such as syntactic dependency relationships and head words,
since only simple lexical features are used in thecurrent incarnation.

References
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014. Neural machine translation by jointly
learning to align and translate. arXiv preprint
arXiv:1409.0473.
Lei Cui, Dongdong Zhang, Mu Li, Ming Zhou, andTiejun Zhao. 2010. A joint rule selection model for
hierarchical phrase-based translation. In Proc. ACL,
pages 6–11.
Jacob Devlin, Rabih Zbib, Zhongqiang Huang, Thomas
Lamar, Richard Schwartz, and John Makhoul. 2014.
Fast and robust neural network joint models for statistical machine translation. In Proc. ACL, pages
1370–1380.
Nadir Durrani, Alexander Fraser, and Helmut Schmid.
2013. Model with minimal translation units, but decode with phrases. In Proc. HLT-NAACL, pages 1–
11.

Akiko Eriguchi, Kazuma Hashimoto, and Yoshimasa Tsuruoka. 2016. Tree-to-sequence attentional neural machine translation. arXiv preprint
arXiv:1603.06075.
Michel Galley, Mark Hopkins, Kevin Knight, andDaniel Marcu. 2004. What’s in a translation rule?
In Proc. HLT-NAACL, pages 273–280.
Michel Galley, Jonathan Graehl, Kevin Knight, Daniel
Marcu, Steve DeNeefe, Wei Wang, and Ignacio
Thayer. 2006. Scalable inference and training ofcontext-rich syntactic translation models. In Proc.
COLING-ACL, pages 961–968.

Haitao Mi, Liang Huang, and Qun Liu. 2008. Forestbased translation. In Proc. HLT-ACL, pages 192–
199.
Graham Neubig. 2013. Travatar: A forest-to-stringmachine translation engine based on tree transducers. In Proc. ACL, pages 91–96.
Franz Josef Och and Hermann Ney. 2003. A systematic comparison of various statistical alignment
models. Computational linguistics, 29(1):19–51.
Franz Josef Och. 2003. Minimum error rate training instatistical machine translation. In Proc. ACL, pages
160–167.

Jianfeng Gao, Xiaodong He, Wen-tau Yih, and
Li Deng. 2014. Learning continuous phrase representations for translation modeling. In Proc. ACL,
pages 699–709.

Holger Schwenk. 2012. Continuous space translation
models for phrase-based statistical machine translation. In Proc. COLING, pages 1071–1080.

Isao Goto, Bin Lu, Ka Po Chow, Eiichiro Sumita, andBenjamin K Tsou. 2011. Overview of the patentmachine translation task at the NTCIR-9 workshop.
In Proc. NTCIR-9, pages 559–578.

Hendra Setiawan, Zhongqiang Huang, Jacob Devlin,
Thomas Lamar, Rabih Zbib, Richard Schwartz, andJohn Makhoul. 2015. Statistical machine translation features with multitask tensor networks. In
Proc. ACL-IJCNLP, pages 31–41.

Jonathan Graehl and Kevin Knight. 2004. Training
tree transducers. In Proc. HLT-NAACL, pages 105–
112.
Zhongjun He, Qun Liu, and Shouxun Lin. 2008. Improving statistical machine translation using lexicalized rule selection. In Proc. Coling, pages 321–328.
Sébastien Jean, Kyunghyun Cho, Roland Memisevic,
and Yoshua Bengio. 2015. On using very large target vocabulary for neural machine translation. In
Proc. ACL-IJCNLP, pages 1–10.
Philipp Koehn. 2004. Statistical significance tests formachine translation evaluation. In Proc. EMNLP,
pages 388–395.

Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014.
Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pages 3104–3112.
Ashish Vaswani, Haitao Mi, Liang Huang, and David
Chiang. 2011. Rule markov models for fast treeto-string translation. In Proc. HLT-ACL, pages 856–
864.
Ashish Vaswani, Yinggong Zhao, Victoria Fossum, andDavid Chiang. 2013. Decoding with large-scaleneural language models improves translation. In
Proc. EMNLP, pages 1387–1392.

Yang Liu, Qun Liu, and Shouxun Lin. 2006. Treeto-string alignment template for statistical machinetranslation. In Proc. COLING-ACL, pages 609–616.

Jiajun Zhang, Shujie Liu, Mu Li, Ming Zhou, andChengqing Zong. 2014. Bilingually-constrainedphrase embeddings for machine translation. In Proc.
ACL, pages 111–121.

Qun Liu, Zhongjun He, Yang Liu, and Shouxun Lin.
2008. Maximum entropy based rule selection model
for syntax-based statistical machine translation. In
Proc. EMNLP, pages 89–97.

Jingyi Zhang, Masao Utiyama, Eiichiro Sumita, Graham Neubig, and Satoshi Nakamura. 2015. A binarized neural network joint model for machine translation. In Proc. EMNLP, pages 2094–2099.

Thang Luong, Hieu Pham, and Christopher D. Manning. 2015a. Effective approaches to attentionbased neural machine translation. In Proc. EMNLP,
pages 1412–1421.

Hai Zhao, Chang-Ning Huang, and Mu Li. 2006. An
improved chinese word segmentation system withconditional random field. In Proc. SIGHAN, pages
162–165.

Thang Luong, Ilya Sutskever, Quoc Le, Oriol Vinyals,
and Wojciech Zaremba. 2015b. Addressing therare word problem in neural machine translation. In
Proc. ACL-IJCNLP, pages 11–19.
Fandong Meng, Zhengdong Lu, Mingxuan Wang,
Hang Li, Wenbin Jiang, and Qun Liu. 2015. Encoding source language with convolutional neuralnetwork for machine translation. In Proc. ACLIJCNLP, pages 20–30.