言語処理学会 第24回年次大会 発表論文集 (2018年3月)

Structured Common Subsequences
for Automatic Machine Translation Evaluation
Chenchen Ding, Masao Utiyama, Eiichiro Sumita
ASTREC, NICT, Japan{chenchen.ding, mutiyama, eiichiro.sumita}@nict.go.jp

Introduction

longest common subseq. = 3
A

To automatically evaluate the performance of a machine translation (MT) system is no less difficult atask than the automatic translation task itself. The
most widely used measure in research community is
the BLEU score [1], which can be interpreted as anarithmetic mean of the precision on N -gram matching with a brevity penalty, where N usually is up to 4
in practice. As the N -grams used in BLEU are local
features, which cannot reveal the structured information in transltion, metrics applying word order features are proposed. A typical one is RIBES [2], where
word order is measured by Kendall’s τ and combined with weighted uni-gram precisions. RIBES has
shown especially high correlation with human evaluation in translation tasks requiring large amountof reordering operations, e.g., translation of longsentences between English and Japanese. However,
BLEU is still a more human-correlated measure on
those translation tasks not requiring reordering operation so heavily.
In our opinion, how to intuitively combine the local features and global structural features is an important issue in automatic evaluation metrics of MT.
In BLEU, as mentioned, there is no structured features used, while in RIBES, the two kinds of features are combined with specific weights. Once such
hyper-parameters are introduced, metrics then easily
turn task-specific, with loss of generality at a certain
level. Moreover, the meaning of hyper-parameters
are usually hard to interpret. This is an crucial
reason on why BLEU is so widely used despite its
obvious defects. As there is no hyper-parameters,1
BLEU is quite easy and intuitive to interpret, say,even if BLEU has only a mediocre correlation withhuman evaluation, at least we know a high BLEU
score means a high precision on N -gram matching.
In this study, we proposed a measure based on
twice common subsequence matching operation, referred to as double common subsequence (dcs) score.
The first matching provides a component cs1, which
1 Actually, the largest order of N -grams is a parameter, but
a fixed 4 is overwhelmingly adopted.

B

C

D

E
A
B

S1

S1

S2

F
D

S2

𝑆 = reference length × result lengthE

S1

reference length = 5

𝑐𝑠0 =result length = 5

1longest common subseq. 3
=
𝑆
5

𝑐𝑠1 =

σ 𝑆1
6
=
𝑐𝑠2 =
𝑆
5

𝑑𝑐𝑠 =

σ 𝑆1 + σ 𝑆2
8
=
𝑆
5

σ 𝑆2
2
=
𝑆
5

Figure 1: Taking ABCDE as a reference string, several metrics for the string of EABFD. cs0 is a simple
normalized length of longest common subsequence.
cs1, cs2 and dcs can be intuitively interpreted as
the square root of the ratio of corresponding areas.
(S2 are depicted symmetrically as two triangles toindicate it is a kind of “monotone bonus” for subsequences AB and D)
reveals the local features by the length of matchedsubsequences, based on which a second-order matching provides a component cs2, showing the monotone tendency among the matched subsequences.
The dcs score is a geometric mean of cs1 and cs2.
Details of the proposed dcs will be described in Sec. 3
and an example is shown in Fig. 1 for intuitive understanding. Basically, the dcs is still a measure
based on matching of MT output and reference byhuman translation, like BLEU and RIBES. However,
we designed it with special merits as follows.
1. no parameter needed to be tuned
2. applicable on character-level for languages without word separators, e.g., Chinese and Japanese
3. local and structured features combined naturally
We evaluate the proposed measure on translation
tasks at Workshop on Asian Translation (WAT) [3,4, 5, 6]. We have found that cs2 component outperforms RIBES on heavily reordering-required tasks as
English-to-Japanese and Japanese-to-English translations, as well as monotonous translation task of
Korean-to-Japanese. On tasks requiring medium reordering such as Chinese-to-Japanese and Japaneseto-Chinese translation, the dcs score can provide astable performance comparable with BLEU, without
the affects introduced by tokenizing.

― 837 ―

Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

2

Related Work

Besides the mentioned BLEU and RIBES, various
metrics for MT evaluation have been proposed. A
simple and widely used category is to compare one ormore references translated by human with the output
of an automatic MT system. The BLEU and RIBES
are both belong to this category. Other metrics inthis category including editing distance based measures such as TER [7], and a pack of recall based measures called ROUGE [8] (or ORANGE [9], for several common sequence based metrics). More sophisticated metrics may rely on linguistic analysis wherea typical measure is METEOR [10, 11]. Metrics inthis category generally require well prepared monolingual data. Another line of research is referencefree evaluation, where evaluation models are trained
from parallel data. A recently proposed measure is
AMFM [12]. This kind of metrics can capture deeper
semantic features but requires considerable parallel
data to train numerous parameters.

3

Proposed Method

The proposed method is inspired by ROUGE-L [8],which is a measure by longest common subsequences(LCS) between reference and MT output. As addressed, the combination of local and structured features is an important issue for evaluation metrics.
The LCS can thus combine the two kinds of features
to a certain extent. However, there are still limitations by simple LCS as, 1) the granularity of matchedstrings are not addressed enough and 2) the nonmonotone matched parts are not taken into consideration. For 1), an improved ROUGE-W [8] has been
proposed to weight longer continuous subsequencesmore, while 2) is an intrinsic problem of LCS that it
can only choose one path in matching, and features
not lying on the optimal path are all neglected.
We improve LCS-based methods in two steps.
First, rather than the optimal longest path in LCS
is considered, we take all non-nested common subsequences into consideration. That is, we collect all local continuous matched subsequences no matter the
relative order among them. Taking Fig. 1 as an example, there are three such subsequences of AB,2 D,
and E. Notice the subsequence of E will be omitted if
only the LCS (i.e., ABD) is considered. Such a set ofcommon subsequences can provide a more complete
set of local matching features, while the structured
information contained in LCS is lost. Therefore, asecond common subsequence matching is conducted
to filter out the monotonous parts within the resultsof the first matching. The basic unit in the second
matching is the subsequences obtained in the first
2 A and B are also common subsequences while they are thenested parts of AB.

matching, e.g., the (AB, D) pair is identified as amonotonous pair in Fig. 1. Hence, the structured
information lost in the first matching is brought inby the second matching.3
Based on the two steps of matching, we can calculate two components for local and structured features respectively. Inspired by the weighting method
in ROUGE-W and intuitiveness, we set the overall framework in a quadratic manner. As shownin Fig. 1, the cs1 component for local features is
the square root of the summation over the squared
lengths for all subsequences in the first matching; thecs2 component for structured features is the squareroot of the summation over terms proportional to
the lengths of neighboring monotonous subsequence
identified in the√ second matching; and an overall
dcs is equal to cs12 + cs22 . Considering two common subsequences with lengths of x and y, because(x + y)2 > x2 + xy + y 2 > x2 + y 2 is always true
when x > 0, y > 0, dcs most appreciates long andcontinuous common subsequences (i.e., when the two
subsequences are concatenated to one with a lengthof (x+y)), and moderately appreciates common subsequences with a monotonous order (i.e., there is an
extra xy term added to x2 + y 2 , which, after all, cannot be larger than (x + y)2 ).4 The Python codes5 of
our implementation of dcs is presented in Table 1.

4

Evaluation

We selected tasks having no less than ten attending teams at WAT and calculated the Pearson’s ρ
between the human-evaluation score and automatic
metrics. The official evaluation metrics in WAT are
BLEU, RIBES, and AMFM. The BLEU and RIBES
for Chinese and Japanese are based on different tokenizers, while AMFM are character-based. For tasks
with the two languages as target language, we also
added character-based BLEU of 4- and 8-grams incomparison. As to the proposed methods using common subsequences, we first tested the simplest LCSbased measure, i.e., cs0 in Fig. 1. This measure isessentially identical to ROUGH-L but the normalization way on sentence length is slightly different.
The dcs and its components of cs1 and cs2 areevaluated respectively. All the common subsequencebased measures were conducted on character-level
for Chinese and Japanese. Text normalization on
digits and punctuation marks were according to the
instruction of the WAT.
3 The second step matching may provide more structured
features than LCS, because it is possible to have monotonous
subsequences away from the optimal path.
4 If the xy term is weighted in (0, 2), the relation is still true
and we will have a dcs with weighted cs1 and cs2.
5 Executable under Python 2.x. As the filter () does not
return a list in Python 3.x, slight modification will be needed.

― 838 ―

Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

def nosub (x, y, s) :good = []; xm, ym = [1 for i in x], [1 for i in y]; xp, yp = [0 for i in x], [0 for i in y]s.sort (key = lambda x : -(len (x [0])))for i,j in s :X, Y, L = j [0], j [1], len (i)if sum (xm [X-L:X]) and sum (ym [Y-L:Y]) :xm [X-L:X], ym [Y-L:Y] = xp [X-L:X], yp [Y-L:Y]; good.append ([i,j])return good
def rank (s) :s.sort (key = lambda x : x [-1][0]); for i in range (len (s)) : s [i][-1][0] = i+1
s.sort (key = lambda x : x [-1][-1]); for i in range (len (s)) : s [i][-1][-1] = i+1
return dict ([(tuple (j),i) for i,j in s])
def score (ss, s, x, y) :A, S0, S1, S2 = (len (x) * len (y)) ** 0.5, [0.], 0., 0.
for i in ss :S0.append (sum ([len (s [x]) for x in i]))for j in range (len (i)) : S1 += len (s [i [j]]) ** 2for j in range (len (i)-1) : S2 += len (s [i [j]]) * len (s [i [j+1]])
return max (S0)/A, (S1**0.5)/A, (S2**0.5)/A, ((S1+S2)**0.5)/A
def table (lx, ly) : return [[[] for j in range (ly+1)] for i in range (lx+1)]
def prod (lx, ly) : return [(i,j) for j in range (1,ly+1) for i in range (1,lx+1)]
def dcs (x, y) :if not x or not y : return 0., 0., 0., 0.,t, p = table (len (x), len (y)), prod (len (x), len (y)) # 1st cs
for (i,j) in p :if x [i-1] == y [j-1] : t [i][j], t [i-1][j-1] = t [i-1][j-1]+[x [i-1]], []s = rank (nosub (x, y, filter (lambda x : x [0], [[t [i][j], [i,j]] for (i,j) in p])))t, p = table (len (s), len (s)), prod (len (s), len (s)) # 2nd cs
for i in s : t [i [0]][i [1]] = [i]for (i,j) in p :if t [i][j] : t [i][j], t [i-1][j-1] = t [i-1][j-1]+t [i][j], []return score (filter (lambda x : x, [t [i][j] for (i,j) in p]), s, x, y)

Table 1: Python implementation of dcs. Two parameters of dcs () are the two strings under comparison. Fourscores will be returned by dcs (), in the order of cs0, cs1, cs2, and dcs as illustrated in Fig. 1.
The numerical results are listed from Tables 2 to 5.
Generally, in tasks requiring heavy reordering as
English-to-Japanese and Japanese-to-English translation (Tables 2 and 4), cs2 has the best performancein most cases, even better than RIBES. An interesting fact is that, on the Korean-to-Japanese translation (right at Table 5), which is a task nearly requiring no reordering, cs2 is the only measure givesa moderately positive performance. It seems cs2
is quite suitable for translation tasks with extreme
operations, no matter heavy or none, on word reordering. However, on tasks requiring moderate reordering such as Chinese-to-Japanese and Japaneseto-Chinese translation, dcs gives a more stable performance. Notice LCS-based cs0 is not bad a measure considering the simplicity, and cs1 itself is not
so good a measure in most cases because it does notcontain much structured information.
The correlation between human-evaluation andautomatic metrics may be affected by various factors.
It is obvious that the ASPEC-16 in Tables 2 and4 has very low ρ’s. We consider it is because mostteams switched to NMT approaches from this year.
In Table 3, the ASPEC and JPC tasks show different tendencies among metrics, where it seems the
ASPEC task requires more word reordering thanthat in JPC task. As mentioned, the automatic
evaluation itself is a non-trivial task, we consider thedcs score (and the cs2 in it) provides an alternative
method which is intuitive and efficient enough.

5

Conclusion

We proposed an MT evaluation measure of dcs score.
From the evaluation on WAT tasks, dcs shows comparable performances as BLEU and its cs2 component is better than RIBES. We plan to investigate
the feasibility of the method in future WAT tasks.

References[1] K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu,
“BLEU: A method for automatic evaluation of machine translation,” in Proc. of ACL, pp. 311–318,
2002.
[2] H. Isozaki, T. Hirao, K. Duh, K. Sudoh, and
H. Tsukada, “Automatic evaluation of translation
quality for distant language pairs,” in Proc. of
EMNLP, pp. 944–952, 2010.
[3] T. Nakazawa, H. Mino, I. Goto, S. Kurohashi, andE. Sumita, “Overview of the 1st workshop on Asiantranslation,” in Proc. of WAT, pp. 1–19, 2014.
[4] T. Nakazawa, H. Mino, I. Goto, G. Neubig, S. Kurohashi, and E. Sumita, “Overview of the 2nd workshop on Asian translation,” in Proc. of WAT, pp. 1–
28, 2015.
[5] T. Nakazawa, H. Mino, C. Ding, I. Goto, G. Neubig,
S. Kurohashi, and E. Sumita, “Overview of the 3rdworkshop on Asian translation,” in Proc. of WAT,
pp. 1–46, 2016.
[6] T. Nakazawa, S. Higashiyama, C. Ding, H. Mino,
I. Goto, H. Kazawa, Y. Oda, G. Neubig, and― 839 ―

Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

ASPEC-14
cs2
RIBES-juman
RIBES-mecab
cs0
RIBES-kytea
dcs
BLEU-char-8
cs1
BLEU-char-4
BLEU-mecab
BLEU-kytea
BLEU-juman
AMFM

ρ
.90
.87
.86
.85
.85
.71
.71
.66
.65
.64
.64
.64
.63

ASPEC-15
cs2
RIBES-mecab
RIBES-kytea
RIBES-jumancs0
dcs
BLEU-char-8
cs1
BLEU-kytea
BLEU-juman
BLEU-mecab
BLEU-char-4
AMFM

ρ
.95
.95
.95
.95
.89
.72
.69
.64
.62
.62
.61
.55
.19

ASPEC-16
AMFM
BLEU-char-4
cs2
BLEU-char-8
cs0
dcs
BLEU-jumancs1
BLEU-mecab
RIBES-juman
BLEU-kytea
RIBES-mecab
RIBES-kytea

ρ
.48
.33
.32
.26
.20
.15
.14
.12
.12
.10
.10
.09
.08

ASPEC-17
BLEU-char-8
BLEU-char-4
BLEU-kytea
RIBES-mecab
RIBES-juman
cs1
cs0
dcs
BLEU-mecab
BLEU-juman
RIBES-kytea
cs2
AMFM

ρ
.97
.96
.95
.94
.94
.94
.94
.93
.93
.93
.92
.87
.69

JPC-16
cs2
RIBES-mecab
RIBES-kytea
RIBES-jumancs0
BLEU-kytea
BLEU-char-4
BLEU-juman
AMFM
BLEU-mecab
BLEU-char-8
dcs
cs1

ρ
.77
.67
.67
.66
.61
.61
.60
.58
.58
.57
.54
.48
.42

JPC-16cs1
dcs
RIBES-mecab
RIBES-kytea
BLEU-mecab
BLEU-kytea
BLEU-juman
RIBES-jumancs0
BLEU-char-8
cs2
BLEU-char-4
AMFM

ρ
.98
.98
.98
.98
.98
.98
.98
.97
.96
.96
.94
.93
.93

Table 2: Pearson’s ρ on English-to-Japanese tasks.
ASPEC-14
cs0
cs2
dcs
BLEU-kytea
cs1
BLEU-char-8
BLEU-mecab
BLEU-juman
BLEU-char-4
RIBES-mecab
RIBES-kytea
RIBES-juman
AMFM

ρ
.94
.93
.90
.90
.89
.89
.89
.89
.87
.85
.85
.84
.80

ASPEC-15
cs2
cs0
BLEU-kytea
dcs
cs1
BLEU-char-8
BLEU-mecab
BLEU-juman
BLEU-char-4
AMFM
RIBES-kytea
RIBES-mecab
RIBES-juman

ρ
.94
.94
.94
.93
.93
.93
.93
.93
.92
.91
.88
.87
.86

ASPEC-16
cs2
RIBES-kytea
RIBES-mecab
RIBES-jumancs0
dcs
BLEU-kytea
BLEU-char-4
BLEU-mecab
BLEU-jumancs1
BLEU-char-8
AMFM

ρ
.96
.96
.95
.95
.94
.91
.91
.90
.90
.90
.89
.89
.88

JPC-15
cs1
dcs
BLEU-char-8
BLEU-kytea
BLEU-jumancs0
BLEU-char-4
BLEU-mecab
RIBES-mecab
RIBES-kytea
RIBES-juman
cs2
AMFM

ρ
.93
.93
.93
.93
.93
.92
.92
.92
.91
.91
.91
.89
.89

Table 3: Pearson’s ρ on Chinese-to-Japanese tasks.
14
cs2
cs0
RIBES
dcs
BLEU
cs1
AMFM

ρ
.90
.89
.88
.75
.68
.63
.28

15
cs2
RIBES
cs0
dcs
BLEU
cs1
AMFM

ρ
.90
.88
.88
.81
.79
.74
.58

16
cs2
cs0
RIBES
dcs
cs1
BLEU
AMFM

ρ
.35
.35
.23
.19
.13
.07
−

17
cs2
cs0
BLEU
dcs
cs1
RIBES
AMFM

ASPEC-j2z-14
BLEU-char-8
BLEU-char-4
AMFM
cs1
dcs
BLEU-stdpku
BLEU-stdctb
BLEU-kytea
RIBES-stdpku
RIBES-stdctb
RIBES-kytea
cs0
cs2

ρ
.97
.97
.97
.96
.95
.93
.29

Table 4: Pearson’s ρ on Japanese-to-English tasks.
(ASPEC, “−” means ρ < 0)
S. Kurohashi, “Overview of the 4th workshop on
Asian translation,” in Proc. of WAT, pp. 1–54, 2017.
[7] M. Snover, B. Dorr, R. Schwartz, L. Micciulla, andJ. Makhoul, “A study of translation edit rate withtargeted human annotation,” in Proc. of AMTA,
pp. 223–231, 2006.
[8] C.-Y. Lin, “ROUGE: A package for automatic evaluation of summaries,” in Proc. of ACL workshop:
Text summarization branches out, 2004.
[9] C.-Y. Lin and F. J. Och, “Orange: A method forevaluating automatic evaluation metrics for machinetranslation,” in Proc. of COLING, 2004.
[10] S. Banerjee and A. Lavie, “METEOR: An automatic
metric for MT evaluation with improved correlation
with human judgments,” in Proc of ACL workshop
on intrinsic and extrinsic evaluation measures for

ρ
.75
.74
.74
.73
.71
.71
.71
.70
.63
.62
.62
.61
.57

JPC-k2j-15
cs2
cs0
RIBES-kytea
RIBES-mecab
RIBES-juman
AMFM
BLEU-char-4
BLEU-char-8
BLEU-kytea
BLEU-mecab
BLEU-juman
dcs
cs1

ρ
.51
−
−
−
−
−
−
−
−
−
−
−
−

Table 5: Pearson’s ρ on Japanese-to-Chinese (left)
and Korean-to-Japanese (right) tasks. (“−” means
ρ < 0)
machine translation and/or summarization, pp. 65–
72, 2005.
[11] A. Lavie and A. Agarwal, “METEOR: An automatic
metric for mt evaluation with improved correlation
with human judgments,” in Proc. of WMT, pp. 228–
231, 2007.
[12] R. E. Banchs, L. F. D’Haro, and H. Li, “Adequacyfluency metrics: Evaluating MT in the continuous
space model framework,” IEEE TASLP, vol. 23,
no. 3, pp. 472–482, 2015.

― 840 ―

Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.