Machine Translation manuscript No.
(will be inserted by the editor)

Substring-based Machine Translation
Graham Neubig · Taro Watanabe ·Shinsuke Mori · Tatsuya Kawahara

Received: date / Accepted: date

Abstract Machine translation is traditionally formulated as the transductionof strings of words from the source to the target language. As a result, additional lexical processing steps such as morphological analysis, transliteration,and tokenization are required to process the internal structure of words tohelp cope with data-sparsity issues that occur when simply dividing words
according to white spaces. In this paper, we take a diﬀerent approach: notdividing lexical processing and translation into two steps, but simply viewing
translation as a single transduction between character strings in the source
and target languages. In particular, we demonstrate that the key to achieving
accuracies on a par with word-based translation in the character-based framework is the use of a many-to-many alignment strategy that can accurately capture correspondences between arbitrary substrings. We build on the alignment
method proposed in Neubig et al (2011), improving its eﬃciency and accuracy
with a focus on character-based translation. Using a many-to-many aligner
imbued with these improvements, we demonstrate that the traditional framework of phrase-based machine translation sees large gains in accuracy overcharacter-based translation with more naive alignment methods, and achieves
comparable results to word-based translation for two distant language pairs.
Keywords character-based translation · alignment · inversion transduction
grammarG. Neubig
Nara Institute of Science and Technology
8916-5 Takayama-cho, Ikoma, Nara, Japan
E-mail: neubig@is.naist.jp
T. Watanabe
National Institute of Information and Communications Technology
3-5 Hikari-dai, Seika-cho, Soraku-gun, Kyoto, Japan
S. Mori and T. Kawahara
Kyoto University
Yoshida Honmachi, Sakyo-ku, Kyoto, Japan2

Graham Neubig et al.

1 Introduction
Statistical machine translation (SMT) is generally treated as the task of translating a source-language sentence f J1 to a target-language sentence eI1 , where
each element of fj and ei is assumed to be a word in the source and target languages. However, the deﬁnition of “word” is often problematic. The
most obvious example of this is in unsegmented languages such as Chinese,
Japanese, or Thai, where word segmentation is a necessary step prior to translation, and it has been noted that the segmentation standard has a large eﬀect
on translation accuracy (Chang et al, 2008). Even for languages with explicit
word boundaries, all MT systems perform at least some cursory form of tokenization, splitting punctuation and words to prevent the sparsity that would
occur if punctuated and non-punctuated words were treated as diﬀerent entities. Sparsity also manifests itself in a number of other forms, with an extremely large number of rare words existing due to morphological productivity,
word compounding, numbers, and proper names. A myriad of methods havebeen proposed to handle each of these phenomena individually in the context of MT, including morphological analysis, stemming, compound breaking,number regularization, word segmentation optimization, and transliteration,
which are outlined in more detail in Section 2.
These diﬃculties stem from the basic premise that we are translating sequences of words as our basic unit. On the other hand, Vilar et al (2007)
examine the possibilities of eschewing the concept of words, treating each sentence as sequences of characters to be translated. This method is attractive,
as it is theoretically able to handle almost all sparsity phenomena in a single
uniﬁed framework, but has only proven feasible between similar language pairs
such as Spanish–Catalan (Vilar et al, 2007), Swedish–Norwegian (Tiedemann,2009), and Thai–Lao (Sornlertlamvanich et al, 2008), which have a large number of cognates and a strong co-occurrence between single characters. As Xu
et al (2004) and Vilar et al (2007) state and we further conﬁrm here, accurate translations cannot be achieved when simply applying the traditional MT
pipeline to character-based translation for less similar language pairs.
This paper is an extension of our work presented in Neubig et al (2012),
supplemented with a more complete description of the proposed alignment
technique, additional experimental results investigating the eﬀect of varying
reordering limits or using character strings on only one side of the translation,
and a subjective analysis of what type of alignments beneﬁt or suﬀer whenusing character strings. We propose improvements to character-based translation, and demonstrate that it is, in fact, possible to achieve competitivetranslation accuracy for distant language pairs using only character strings.
In particular, we focus on the bitext alignment process, and demonstrate thatpoor alignments achieved by more traditional alignment methods are one of
the major reasons for character-based alignment failing to generalize to distant language pairs in previous work. We then propose an improved alignment
strategy for character-based translation, which is made possible through recent
advances in many-to-many word alignment, which we overview in Section 3.

Substring-based Machine Translation

3

In comparison with the popular one-to-many IBM alignment models (Brown
et al, 1993; Och and Ney, 2003) used in previous work on character-basedtranslation, many-to-many alignment can choose to align arbitrary substrings,
which may consist of characters, morphemes, words, or multi-word phrases,
automatically adjusting the granularity of alignment based on the paucity or
abundance of data available.
One barrier to applying many-to-many alignment models to character
strings is training cost. In the inversion transduction grammar (ITG) framework (Wu, 1997), used in many previous works in many-to-many alignment,
search is cumbersome for longer sentences, a problem that is further exacerbated when using characters instead of words as the basic unit. Even with more
eﬃcient search techniques for phrasal ITGs such as those proposed by Saers
et al (2009) or Blunsom and Cohn (2010), most previous research has limited
the number of words in a sentence to at most 40. In order to overcome this computational burden and make character-based alignment feasible, we propose
two improvements to the alignment model. The ﬁrst proposed improvement,
described in Section 4.3, increases the eﬃciency of the beam-search techniqueof Saers et al (2009) by augmenting it with look-ahead probabilities in thespirit of A* search. As a heuristic function, we consider the monolingual costof covering the strings in the source and target languages independently, which
can be calculated eﬃciently but provides a reasonable estimate of the bilingualalignment cost.
A second problem with existing many-to-many alignment models in thecontext of character-based translation lies in the fact that they use one-tomany alignment models to seed the many-to-many alignment models in theform of a prior probability over the phrase pair distribution. While this has
proven critical for accuracy in many-to-many systems for word-based translation (DeNero et al, 2008), in the character-based context one-to-many probabilities are not reliable. The second proposed improvement, described in Section 5, seeds the search process using counts of all substring pairs in the corpus
to bias the phrase alignment model. We present an eﬃcient method to calculatethese substring pairs using enhanced suﬃx arrays (Abouelhoda et al, 2004) andsparse matrix operations. After these statistics have been collected, we transform them into prior probabilities and use them to seed the less eﬃcient, butmore accurate Bayesian ITG-based many-to-many alignment model.
Finally, to evaluate the eﬀectiveness of the method, we perform end-to-end
MT experiments on four language pairs with diﬀering morphological properties. The evaluation results presented in Section 6 show that for distantlanguage pairs, character-based SMT can achieve translation accuracy that iscomparable to word-based systems. In addition, ablation studies show that theuse of our proposed look-ahead parsing technique as well as substring-basedpriors both signiﬁcantly help accuracy, and the look-ahead parsing method
doubles the speed of alignment. Finally, we perform a qualitative analysis of
the translation results that shows that the character-based method is not only
able to translate unsegmented text, conjugated words, and proper names in a4Graham Neubig et al.

uniﬁed framework, but also uses a larger fraction of locally correct translation
rules than word-based translation.

2 Related Work on Lexical Processing in SMT
As traditional SMT systems treat all words as single tokens without considering their internal structure, major problems of data sparsity occur for lessfrequent tokens. In fact, it has been shown that there is a direct negative correlation between vocabulary size (and thus sparsity) of a language and translation accuracy (Koehn, 2005). Rare words causes trouble for alignment models,
both in the form of incorrect alignments, and in the form of garbage collection,
where rare words in one language are incorrectly aligned to large segments ofthe sentence in the other language (Och and Ney, 2003). Unknown words arealso a problem during the translation process, and the default approach is to
map them ‘as is’ into the translated sentence.
This is a major problem in morphologically rich languages such as Finnish
and Korean, as well as highly compounding languages such as Dutch andGerman. Many previous works have attempted to handle morphology, decompounding and regularization through lemmatization, morphological analysis,or unsupervised techniques (Nießen and Ney, 2000; Brown, 2002; Lee, 2004;
Goldwater and McClosky, 2005; Talbot and Osborne, 2006; Macherey et al,2011). Other research has noted that it is more diﬃcult to translate into morphologically rich languages with word-based systems, and methods for modeling target-side morphology have attracted interest in recent years (Bojar, 2007;
Subotin, 2011). It is also notable that morphology and compounding remain
problematic regardless of the size of the training data, with systems trainedon hundreds of millions of words still seeing signiﬁcant gains in accuracy due
to lexical processing (Macherey et al, 2011).
Another major source of rare words in all languages is proper names, whichhave been handled by using cognates or transliteration to improve translation(Knight and Graehl, 1998; Kondrak et al, 2003; Li et al, 2004; Finch andSumita, 2007). More sophisticated methods for named entity translation thatcombine translation and transliteration have also been proposed (Al-Onaizan
and Knight, 2002). In addition, while transliteration uses the underlying phonetic similarity of proper names to translate between writing systems, there has
also recently been work on direct phoneme-to-word speech translation with the
motivation of improving robustness to speech recognition errors (Jiang et al,2011).
Choosing word units is also essential for creating good translation results
for languages that do not explicitly mark word boundaries, such as Chinese,
Japanese, and Thai. A number of works have addressed this word segmentation problem in translation, mainly focusing on translation of unsegmented
languages such as Chinese or Japanese (Bai et al, 2008; Chang et al, 2008;
Zhang et al, 2008b; Chung and Gildea, 2009; Nguyen et al, 2010; Wang et al,
2010; Chu et al, 2012). However, these works generally assume that a wordSubstring-based Machine Translation

5

segmentation exists in one language (e.g. English) and attempt to optimize theword segmentation in the other language (e.g. Chinese). There have also been
a number of works which propose evaluation measures for these languages thatconsider matches over characters instead of words (Denoual and Lepage, 2005;
Li et al, 2011; Liu and Ng, 2012).
This enumeration of related work demonstrates the range of problems
caused by the concept of ‘words’ in MT, and the large number of solutions proposed to address these problems. Character-based translation has the potential
to handle all of the phenomena in the previously mentioned research in a single
uniﬁed framework, while at the same time requiring no language-speciﬁc tools
such as morphological analyzers or word segmenters. However, while the approach is conceptually attractive, previous research has only been shown to beeﬀective for closely related language pairs (Vilar et al, 2007; Sornlertlamvanich
et al, 2008; Tiedemann, 2009, 2012), or when word- and character-based alignment is combined (Nakov and Tiedemann, 2012). This work proposes eﬀectivealignment and decoding techniques that allow character-based translation toachieve accurate results for both close and distant language pairs. It should
also be noted that there are other many-to-many alignment methods that havebeen used for simultaneously discovering morphological boundaries over multiple languages (Snyder and Barzilay, 2008; Naradowsky and Toutanova, 2011),
but these have generally been applied to single words or short phrases, and it
is not immediately clear that they will scale to aligning full sentences.
3 Alignment Methods
SMT systems are generally constructed from a parallel corpus consisting oftarget-language sentences E and source-language sentences F. The ﬁrst stepof training is to ﬁnd alignments A, which indicate which parts of the target
sentence align to which parts of the source sentence.
Here, we will represent our target and source sentences as eI1 and f J1 . ei andfj represent single elements of the target and source sentences respectively, and
I and J indicate the number of elements in the target and source sentences.
Each element may be a word in word-based alignment models or a single
character in character-based alignment models.1 We deﬁne our alignment asaK
1 , where each element is a span ak = hs, t, u, vi indicating that the target
string es , . . . , et and source string fu , . . . , fv are alignments of each other.2
3.1 One-to-Many Alignment
The most well-known and widely-used models for bitext alignment are for oneto-many alignment, including the IBM models (Brown et al, 1993) and HMM
1 Some previous work has also performed alignment using morphological analyzers tonormalize or split the sentence into morpheme streams (Corston-Oliver and Gamon, 2004).
2 Null alignments can be represented implicitly with no span in aK covering the unaligned
1
words.

6

Graham Neubig et al.

Fig. 1 Character-based alignments using (a) one-to-many models and (b) many-to-manymodels.

alignment model (Vogel et al, 1996). These models are by nature directional,
attempting to ﬁnd the alignments that maximize the conditional probability ofthe target sentence P (eI1 |f J1 , aK
1 ). For computational reasons, the IBM models
are restricted to aligning each word on the target side to a single word on thesource side. In the formalism presented above, this means that each ei must
be included in at most one span, and for each span u = v. Traditionally, thesemodels are run in both directions and combined using heuristics to create
many-to-many alignments (Koehn et al, 2003).
However, in order for one-to-many alignment methods to be eﬀective, eachelement fj must contain enough information to allow for eﬀective alignment
with its corresponding elements in eI1 . While this is often the case in wordbased models, for character-based models this assumption breaks down, as
there is generally no clear correspondence between single characters.
An example of the alignments that result when applying one-to-many alignment to character strings is shown in Figure 1(a). It can be seen that in general, the alignments are less than desirable, with only cognates with similarspellings (e.g. “projects” and “projets”) being aligned properly. The remaining
words are not aligned properly, and a number of spurious alignment links are
introduced, preventing even some of the properly aligned cognates from being
extracted correctly.

3.2 Many-to-Many Alignment
On the other hand, in recent years, there have been advances in many-to-manyalignment techniques that are able to align multi-element chunks on both
source and target sides (Marcu and Wong, 2002; DeNero et al, 2008; Blunsom
et al, 2009; Neubig et al, 2011; Levenberg et al, 2012). Many-to-many methods

Substring-based Machine Translation

7

can be expected to achieve superior results when applied to character-basedalignment, as the aligner can use information about substrings, which may
correspond to single characters, morphemes, words, or short phrases. An example of alignments acquired using the many-to-many models described inlater sections is shown in Figure 1(b). From this example it can be conﬁrmedthat the alignments are not only of higher quality than those obtained by
one-to-many alignment models, but also in units that correspond to humanintuition: words (“project”/“projet”), phrases (“both”/“les deux”), sub-words(“ious”/“ieux”). The above example also shows the somewhat surprising alignment “ s are”/“ s sont”, in which the plural suﬃx of the noun and the pluralform of the copula are combined into a single phrase, capturing agreement
between the two words.
Given our objective of ﬁnding multi-character alignments over character
strings, there are a number of requirements for the alignment model that canbe used.
1. Eﬃciency: The number of characters in a sentence is greater than thenumber of words in a sentence, so an alignment model that can handle
longer sentences becomes a greater concern.
2. Automatic Granularity Adjustment: Given that it is possible to ﬁndalignments of any number of granularities, we must be able to choose anappropriate size based on the amount of data at our disposal. If we havemore data, we can use longer units to achieve more accurate alignments,
and if we have less data, we can fall back to sub-words or characters tomaintain robustness.
3. Compact Translation Model: When performing word-based translation, phrases are generally restricted to a maximum size of around sevenwords. However, for character-based translation, seven characters is notenough to achieve reasonable accuracy, so we would like a model that canutilize longer phrases without creating enormous and unwieldy translation
models.
Out of the many-to-many alignment methods proposed in the literature,
the model we introduced in Neubig et al (2011) satisﬁes most of these desiderata. In order to achieve eﬃcient many-to-many alignment, it formulates thealignment process using ITGs (Wu, 1997), which allow for many-to-manyalignment through biparsing (described in the following section) in polynomial time. In order to automatically adjust the granularity of alignment, alignment model probabilities are calculated according to non-parametric Bayesianstatistics, which allows for a balance between complex, expressive models thatmemorize long segments, and small but less expressive models that use shorter
segments. Finally, the method reduces the translation model size by not using
all phrases licensed by alignments as is typically done in traditional translation
systems (Koehn et al, 2003), but only those licensed by the ITG tree.
This model is trained using Gibbs sampling in a multi-step process thatcan be very simply outlined below (readers may refer to Neubig et al (2011)
for more details):

8

Graham Neubig et al.

Fig. 2 An example of (a) an inversion transduction grammar (ITG) derivation tree, (b) its
corresponding alignment matrix.

1. Calculate prior probabilities with a less accurate but highly eﬃcientalignment model (such as IBM Model 1 (Brown et al, 1993)).
2. Sample alignments A for each sentence:(a) Remove statistics from the model for the current sentence.
(b) Biparse the two sentences according to the current ITG statistics.
(c) Sample a new alignment using the information from the parse andadd the statistics back into the model.
While previous work has shown this model to be eﬀective for word-basedalignment, in this paper we examine its eﬀectiveness with regards to characterbased alignment, and propose two improvements that are described in detailin the following sections. In particular, Section 4.3 describes an improvement
to the biparsing step that improves the eﬃciency and accuracy for long sentences, while Section 5 describes improvements to the step of calculating priorprobabilities using substring co-occurrence statistics.
4 Eﬃcient Sampling of ITG-Based Many-to-Many Alignments
In this section we brieﬂy explain the process of alignment in the ITG framework, describe the process of biparsing that is used to ﬁnd these alignments,
and ﬁnally touch upon our proposed method to improve the eﬃciency of biparsing in many-to-many alignment models through the use of look-aheadprobabilities.
4.1 Inversion Transduction Grammars (ITGs)
ITGs are generative models that were designed to simultaneously describe
the generative process of equivalent strings of tokens e and f in two diﬀer-

Substring-based Machine Translation

9

ent languages. They are a limited form of synchronous context-free grammar(SCFG) in Chomsky normal form (Chomsky, 1956), where “synchronous” indicates that the grammar is deﬁned over two languages instead of one. Figure2(a) shows an example of the word-based ITG derivation that has generated
two phrases “to admit it” and “de le admettre” in English and French, which
we will use to demonstrate how ITGs work. The ITG describes how these
two equivalent sentences were created through a recursive process that passes
through two phases.
The ﬁrst phase consists of generating the sentence structure, which in thecase of ITGs is particularly important for specifying the reordering that occurs
between the sentences in the two languages. It can be seen from the reorderingmatrix in Figure 2(b) that for some phrase pairs the word order is the same inboth languages (“to” precedes “admit it” and “de” precedes “le admettre”).
On the other hand, there are also some places where the order is inverted(“admit” precedes “it” while “admettre” follows “le”). ITGs represent thisreordering structure as a binary tree, with each internal node labeled as straight(str) or inverted (inv), where each of these node types represents the casewhere the order is the same or inverted in both languages, respectively.3 Much
like standard CFGs, each leaf node is labeled with the pre-terminal (term)
to indicate that we have ﬁnished the ﬁrst step of generating the sentence
structure.
The second phase takes place after generating the pre-terminal symbol,
and consists of generating short parallel phrases. These phrases can be oneto-one alignments as shown in the above example, but can just as easily be
one-to-many or many-to-many alignments without a signiﬁcant increase in thetime required for alignment.
In addition, by assigning a probability to each of the ITG productions, it ispossible to create a generative model for parallel phrase pairs. The ITG generative probability can be characterized by Px (x), which is a distribution overnon- and pre-terminals, and Pt (he, f i), which is a distribution over parallelphrase pairs. In this work, we follow the model of Neubig et al (2011) which
deﬁnes the probability through a hierarchical backoﬀ scheme that attempts togenerate parallel phrase pairs from Pt (he, f i), but smooths the probability of
longer phrase pairs by combining shorter phrase pairs in the order speciﬁedby the non-terminals generated by Px (x).
ITG-based models can be used to ﬁnd alignments for words in parallel sentences through the process of biparsing (Wu, 1997). Within the ITG framework, a sentence pair heI1 , f J1 i can be deﬁned as the phrase pair that is generated by the node at the top of the derivation tree. Biparsing for ITGs ﬁnds
the most likely derivation for this sentence pair given the ITG probabilities.
Once we have this most likely derivation, we treat all phrase pairs that were3 Here we are speciﬁcally referring to a special case of ITGs with only a single symbol eachfor straight and inverted productions, which is also known as the bracketing ITG. ITGs withmultiple straight and inverted terminals are also conceivable, but are generally not used inalignment as they signiﬁcantly increase the computational burden of learning the ITG.

10

Graham Neubig et al.

Fig. 3 (a) A chart with inside log probabilities I(s, t, u, v) in boxes and forward/backward
look-ahead log probabilities marking surrounding arrows. (b) Spans with corresponding lookahead probabilities added, and the minimum probability underlined. Light and dark shadedspans will be trimmed when the beam is log(P ) ≥ −3 and log(P ) ≥ −6 respectively.

generated from the same terminal symbols as aligned (for example, in Figure
2: “to/de,” “admit/admettre,” and “it/le”).

4.2 Biparsing and Beam Biparsing
Biparsing ITGs is quite similar to standard chart parsing algorithms for monolingual PCFGs, eﬃciently calculating marginal probabilities for each span using bottom-up dynamic programming. We deﬁne the chart as a data structurewith a single cell for each alignment as,t,u,v spanning ets and f vu . Each cell has
an accompanying “inside” probability I(as,t,u,v ). This probability is the combination of the generative probability of each phrase pair Pt (ets , f vu ) and thesum of the probabilities over all shorter spans in straight and inverted order,
as in (1):I(as,t,u,v ) =Pt (ets , fuv )∑ ∑+Px (x = str)I(as,S,u,U )I(aS,t,U,v )s≤S≤t u≤U ≤v

+

∑

∑

Px (x = inv)I(as,S,U,v )I(aS,t,u,U )(1)s≤S≤t u≤U ≤v

where Px (x = str) and Px (x = inv) are the probability of straight andinverted ITG productions, respectively. An example of part of the chart used

Substring-based Machine Translation

11

Fig. 4 An example of the ﬁrst three queues used in ITG parsing along with their insideprobabilities. The hypotheses that would be processed if the beam is set to c = 1e − 1 aresurrounded by boxes.

in this bottom-up parsing can be found in Figure 3(a), where we show thecells that have one-to-one alignments.
The exact calculation of these probabilities can be performed in O(n6 )time, where n = max(I, J) is the length of the longer of eI1 and f J1 (Wu, 1997).
This calculation is performed using a dynamic programming algorithm that
separates each of the spans into queues based on their length l = t − s + u − v,
and queues are processed in ascending order of l. An example of the queues
for the ﬁrst three lengths is shown in Figure 4.
The motivation behind this algorithm is that when calculating a particularspan’s inside probability I(as,t,u,v ) according to Equation (1), all of the otherinside spans that we reference on the right-hand side of the equation are shorter
than as,t,u,v itself. Thus, if we process all spans in ascending order of length, it
is simple to calculate these sums for every span in the chart. The computational
complexity of the algorithm is O(n6 ) because Equation (1) must be calculated
for all of the O(n4 ) spans in the sentence, and there are O(n2 ) elements ineach calculation of the sum.
However, exact computation of these probabilities in O(n6 ) time is impractical for all but the shortest sentences. Saers et al (2009) note that in order toincrease the eﬃciency of processing, queues can be trimmed based on a ﬁxed
histogram beam, only processing the b hypotheses with the highest probability
for each queue. Here, we instead utilize a probability beam, expanding only
hypotheses that are more than c times as likely as the best hypothesis â. In
other words, we have a queue discipline based on the inside probability, andall spans ak where I(ak ) < cI(â) are pruned. c is a constant between 0 and 1
describing the width of the beam, and a smaller constant probability will indicate a wider beam. Figure 4 shows an example of this, with boxes surrounding
part of each queue showing the hypotheses that fall within the beam whenc = 10−1 .

12Graham Neubig et al.

It should also be noted that slice sampling has been proposed as a way
to improve eﬃciency in the learning of Bayesian ITGs (Blunsom and Cohn,
2010). Comparing these two methods, slice sampling has the ability to derive
exact samples from the true probability distribution for biparse trees, and thecost of faster parsing time is reﬂected in a larger number of samples required
to converge to a high-probability section of the probability space. In contrast,
beam search is by nature an approximate search method, and removes theguarantees of selecting from the true probability distribution. However, beam
search is also comparatively simple and conducive to introduction of the lookahead probabilities that we introduce in the following section, so we opt touse it instead.4

4.3 Look-ahead Biparsing
While this pruning signiﬁcantly increases the speed of biparsing, this method
is insensitive to the existence of competing hypotheses when performing pruning. Figure 3(a) provides an example of what a competing hypothesis is, andwhy it is unwise to ignore them. Particularly, the alignments “les/1960s” and“les/the” both share the word “les,” and thus cannot both exist in a single
derivation according to the ITG framework. We will call hypotheses that are
mutually exclusive in this manner competing hypotheses. As the probability of“les/1960s” is much lower than its competing hypothesis “les/the,” it is intuitively unlikely to be chosen, and thus a good candidate for pruning. However,its inside probability is the same as that of “années/1960s,” which has no competing hypotheses and thus should not be removed from consideration. Thissection proposes the use of a look-ahead probability to increase the eﬃciencyof this chart parsing by considering competing hypotheses.
In order to take into account competing hypotheses, we can use for ourqueue discipline not only the inside probability I(ak ), but also the outside
probability O(ak ), the probability of generating all spans other than ak , asin A* search for CFGs (Klein and Manning, 2003), and tic-tac-toe pruning
for word-based ITGs (Zhang and Gildea, 2005). As the calculation of the true
outside probability O(ak ) is just as expensive as parsing itself, it is necessary toapproximate this with heuristic function O∗ that can be calculated eﬃciently.
This section proposes a heuristic function that is designed speciﬁcally forphrasal ITGs and is computable with worst-case complexity of n2 , comparedwith the n3 amortized time of the tic-tac-toe pruning algorithm described byZhang et al (2008a). During the calculation of the phrase generation probabil4 It is also likely that the look-ahead probabilities could be integrated into the auxiliary variable sampling function for slice sampling to improve eﬃciency while maintaining
correctness guarantees, an interesting challenge that we will leave to future work.

Substring-based Machine Translation

13

ities Pt , we save the best probability O∗ for each monolingual span.
Oe∗ (s, t) =Of∗ (u, v) =max

Pt (ã)(2)max

Pt (ã)(3){ã=hs̃,t̃,ũ,ṽi;s̃=s,t̃=t}{ã=hs̃,t̃,ũ,ṽi;ũ=u,ṽ=v}

For each language independently, we calculate forward probabilities α andbackward probabilities β. For example, αe (s) is the maximum probability ofthe span (0, s) of e that can be created by concatenating together consecutive
values of Oe∗ , as in (4):αe (s) =max Oe∗ (0, S1 )Oe∗ (S1 , S2 ) . . . Oe∗ (Sx , s).

{S1 ,...,Sx }(4)

Backwards probabilities and probabilities over f can be deﬁned similarly.
These probabilities are calculated for e and f independently, and can be calculated in n2 time by processing each α in ascending order, and each β indescending order in a fashion similar to that of the forward-backward algorithm. Finally, for any span, we deﬁne the outside heuristic as the minimumof the two independent look-ahead probabilities over each language, as in (5):O∗ (as,t,u,v ) = min(αe (s) ∗ βe (t), αf (u) ∗ βf (v)).

(5)

It should be noted that both of the monolingual probabilities are optimistic
estimates of the one-best outside probability O(ak ) (in a manner similar tothe heuristic function in A* search). Thus, taking the minimum of the two is
motivated by the fact that we would like to choose the less optimistic of thetwo as a more accurate estimate of the true one-best probability.
Taking a look again at the example in Figure 3(b), it can be seen thatwhen using these look-ahead probabilities, the relative probability diﬀerence
between the highest probability span “les/the” and the spans “années/1960s”
and “60/1960s” decreases, allowing for tighter beam pruning without losing
these good hypotheses. In contrast, the relative probability of “les/1960s”
remains low, as it is in conﬂict with a high-probability alignment, allowing it
to be discarded.

5 Prior Probabilities
One of the most critical elements to achieving accurate alignments in theprobabilistic ITG is the accuracy of the phrase distribution Pt . Previous workon many-to-many alignment (DeNero et al, 2008; Neubig et al, 2011) helps
achieve more accurate translations through the deﬁnition of a phrase pairprior probability Pbase (ets , f vu ), also referred to as the “base measure”. Thiscan help eﬃciently seed the search process with a bias towards phrase pairsthat satisfy certain properties. In particular, there are three pieces of priorknowledge that we would like to provide through the base measure. First, we
would like to minimize the number of phrases that are not aligned to any

14Graham Neubig et al.

phrase in the other language, as we can assume that most of the phrases will
have some corresponding translation. Second, we would like to bias against
overly long phrases, as these are likely to cause sparsity and hurt generalization
performance when the model is tested on new data. Finally, to the best extent
possible, we would like to provide information about whether phrase pairs arelikely potential alignments. This can be done by using a simpler alignment
model that is more eﬃcient but less accurate than the ITG-based many-tomany alignment model.

5.1 One-to-Many Prior Probabilities
First, we describe a formulation of the base probability similar to that of
DeNero et al (2008), which uses eﬃciently calculable IBM Model 1 probabilities
to seed the ITG translation model. Pbase is ﬁrst calculated by choosing whether
to generate an unaligned phrase pair (where |e| = 0 or |f | = 0) according
to a ﬁxed probability pu . pu should generally be a small value (10−2 in our
experiments) to minimize the number of unaligned phrases. Based on thischoice, we next generate an aligned phrase pair from Pba , or an unaligned
phrase pair from Pbu
For Pba , we follow DeNero et al (2008) in using the geometric mean of unidirectional IBM Model 1 probabilities, deﬁned according to the probabilitiesin (6)–(7):Pba (he, f i) =M0 (he, f i)Ppois (|e|; λ)Ppois (|f |; λ)

(6)
1
2

M0 (he, f i) =(Pm1 (f |e)Puni (e)Pm1 (e|f )Puni (f )) .

(7)

Ppois is the Poisson distribution with the average length parameter λ, wherek represents the phrase length |f | or |e|, as in (8):Ppois (k|λ) =(λ − 1)k−1 −(λ−1)
e.
(k − 1)!

(8)

λ was set to a relatively small value (10−2 in our experiments), which allows
us to bias against overly long phrases.
Puni is the unigram probability of a particular phrase, and Pm1 is theword-based Model 1 (Brown et al, 1993) probability of one phrase given theother. Model 1 probabilities are word-based translation probabilities that help
to indicate whether the words in each phrase are good translations of eachother. The phrase-based Model 1 probability is calculated as in (9):Pm1 (e|f ) =

|e|
∏

|f |
∑
1
Pm1 (ei |fj )|f | + 1 j=0
i=1

(9)

where ei and fj are the i-th and j-th words in phrases e and f respectively, andf0 is a token for null alignments. The word-based probabilities Pm1 (ei |fj ) andPm1 (fj |ei ) are parameters of the model, and can be calculated eﬃciently using

Substring-based Machine Translation15

the expectation maximization algorithm (Brown et al, 1993) before starting
phrase alignment. Following Liang et al (2006), we combine the Model 1 probabilities in both directions using the geometric mean, which assigns a highprobability to spans where both models agree, and lower probability to any
span where any one of the models assigns a low probability.
For Pbu , in the case of |f | = 0, we calculate the probability as in (10):
Pbu (he, f i) = Puni (e)Ppois (|e|; λ)/2.

(10)The probability can be calculated similarly when |e| = 0. Note that Pbu is
divided by 2 as the probability is considering null alignments in both directions.

5.2 Substring-based Prior Probabilities
While the method suggested in the previous section is eﬀective, it is also
highly dependent on the quality of the IBM Model 1 probabilities. However,for reasons previously stated, these methods are less satisfactory when performing character-based alignment, as the amount of information contained ina character does not allow for proper alignment. In this section, we propose
a novel method for using raw substring co-occurrence statistics to bias alignments towards substrings that often co-occur in the entire training corpus.
This is similar to the method of Cromières (2006), but instead of using theseco-occurrence statistics as a heuristic alignment criterion, they are incorporated as a prior probability in a statistical model that can take into accountmutual exclusivity of overlapping substrings in a sentence.
We deﬁne this prior probability using three counts over substrings ce , cf ,and che,f i . ce and cf count the total number of sentences in which the substrings e and f occur, respectively. che,f i is a count of the total number ofsentences in which the substring e occurs on the target side, and f occurs
on the source side.5 We can perform the calculation of these statistics using enhanced suﬃx arrays, a data structure that can eﬃciently calculate all
substrings in a corpus (Abouelhoda et al, 2004).6
While suﬃx arrays allow for eﬃcient calculation of these statistics, storing
all co-occurrence counts che,f i is an unrealistic memory burden for larger corpora. In order to reduce the amount of memory used, each count is discounted
ﬁxed value d, which is set to 5. This has a dual eﬀect of reducing the amountof memory needed to hold co-occurrence counts by removing values for whichche,f i < d, as well as helping to prevent overﬁtting the training data. In addition, we can heuristically prune values for which the conditional probabilities
P (e|f ) or P (f |e) are less than some ﬁxed value, which is set to 0.1 for thereported experiments.
5 It should be noted that we are not counting duplicate occurrences of substrings in asingle sentence. This was a design choice to prevent the over-counting of one-character orvery short strings that tend to occur many times in a single sentence.
6 Using the open-source implementation esaxx http://code.google.com/p/esaxx/

16

Graham Neubig et al.

In preliminary experiments designed to determine how to combine ce , cf ,and che,f i into prior probabilities we tested a number of methods proposed byprevious research including plain co-occurrence counts, the Dice coeﬃcient,and Chi-squared statistics (Cromières, 2006). As a result of these experiments,
we found the most eﬀective to be a new method of deﬁning substring pair
probabilities to be proportional to bidirectional conditional probabilities; asin (11)–(12):Pcooc (e, f ) = Pcooc (e|f )Pcooc (f |e)/Z()()
che,f i − dche,f i − d=/Zcf − dce − d(11)(12)

for all substring pairs where che,f i > d and where Z is a normalization term
equal to that in (13):∑Z=
Pcooc (e|f )Pcooc (f |e).
(13)
{e,f ;che,f i >d}

The motivation for combining the probabilities in this fashion is similar to thatof the base measure in Equation (7), ﬁnding highly reliable alignments thatare supported by both models. The preliminary experiments showed that thebidirectional conditional probability method gave signiﬁcantly better results
than all other methods, so this method will be adopted for the remainder ofthe experiments.
It should be noted that as we are using discounting, many substring pairs
will be given zero probability according to Pcooc . As the prior is only supposed
to bias the model towards good solutions and not explicitly rule out any possibilities, we can instead linearly interpolate the co-occurrence probability withthe one-to-many Model 1 probability, which will give at least some probability
mass to all substring pairs, as in (14):Pbase (e, f ) = λPcooc (e, f ) + (1 − λ)Pm1 (e, f ).

(14)

In order to ﬁnd an appropriate value, we put a Beta prior (α = 1, β = 1) on
the interpolation coeﬃcient λ and learn it during training.

6 Experiments
This section describes experiments over a variety of language pairs designed
to test the eﬀectiveness of the proposed substring-based translation method.

6.1 Experimental Setup
Evaluation was performed on a combination of four languages with English,
using freely available data. The ﬁrst three language pairs, French–English,
German–English, and Finnish–English, used data from EuroParl (Koehn, 2005),

Substring-based Machine Translation

17

Table 1 The number of sentences and words in each corpus for TM and LM training,tuning, and testing.
de-en
Type
TM (en)TM (other)LM (en)LM (other)
Tune (en)Tune (other)
Test (en)Test (other)

Sent
457k
751k
2.00k
2.00k

ﬁ-en
Word
2.80M
2.56M
16.0M
15.3M
58.7k
55.1k
58.0k
54.3k

Sent
467k
717k
2.00k
2.00k

fr-en
Word
3.10M
2.23M
15.5M
11.3M
58.7k
42.0k
58.0k
41.4k

Sent
457k
688k
2.00k
2.00k

ja-en
Word
2.77M
3.05M
13.8M
15.6M
58.7k
67.3k
58.0k
66.2k

Sent
286k
440k
1.24k
2.00k

Word
2.13M
2.34M
11.5M
11.9M
30.8k
34.4k
26.6k
28.5k

with development and test sets designated for the 2005 ACL shared task on
machine translation.7 Experiments were also performed with Japanese–English
Wikipedia articles from the Kyoto Free Translation Task (Neubig, 2011) using
the designated training and tuning sets, and reporting results on the test set.
These languages were chosen as they have a variety of interesting characteristics. French has some level of inﬂection, but among the test languages has
the strongest one-to-one correspondence with English, and is generally considered to be easy to translate. German has many compound words, whichmust be broken apart in order to translate properly into English. Finnish is
an agglutinative language with extremely rich morphology, resulting in longwords and the largest vocabulary of the languages in EuroParl. Japanese does
not have any clear word boundaries, and uses logographic characters, whichcontain more information than phonetic characters.
With regards to data preparation, the EuroParl data was pre-tokenized,
so the experiments simply used the tokenized data ‘as is’ for the training
and evaluation of all models. For word-based translation in the Kyoto task,
training was performed using the tokenization scripts provided. For characterbased translation, no tokenization was performed, using the original text for
both training and decoding. For both tasks, all sentences for which both source
and target were 100 characters or less were selected as training data, the total
size of which is shown in Table 1.8 In character-based translation, white spaces
between words were treated as any other character and not given any special
treatment. Evaluation was performed on tokenized and lower-cased data.
For alignment, GIZA++ (Och and Ney, 2003) was used as an implementation of one-to-many alignment, with pialign used as an implementation of the7

http://www.statmt.org/wpt05/mt-shared-task/.
The 100-character limit results in the use of somewhat shorter sentences than whenusing limits based on words. For example, using a more traditional limit of a maximum of
40 words on both sides for Japanese-English results in a total of 5.91M words of English, 2.7
times greater than when a 100-character limit is used. The 100-character limit was mainly foreﬃcient experimentation in the character-based models, and we describe possible directions
for raising this limit in the future work section.
8

18

Graham Neubig et al.

ITG models9 modiﬁed with the proposed improvements. For GIZA++, thedefault settings were used for word-based alignment, but for character-basedalignment the training process was stopped at the HMM model, omitting IBM
Models 3 and above, as the more advanced models caused training to fail for
longer sentences. For pialign, default settings were used except for characterbased ITG alignment, which used a probability beam of 10−4 instead 10−10 .
Decoding was performed with the Moses decoder (Koehn et al, 2007), withthe default settings except for the stack size, which was set to 1000 insteadof 200. Minimum error rate training (Och, 2003) was performed to maximize
word-based BLEU score for all systems.10 For language models, word-basedtranslation used a word 5-gram model, and character-based translation useda character 12-gram model, both smoothed using interpolated Kneser-Ney
smoothing (Kneser and Ney, 1995).11

6.2 Quantitative Evaluation
This section presents a quantitative analysis of the translation results for eachof the proposed methods. As previous research has shown that it is more diﬃcult to translate into morphologically rich languages than into English (Koehn,2005), experiments are performed to test the accuracy translating in both directions for all language pairs. Translation quality is evaluated using BLEU
score (Papineni et al, 2002), both on the word and character level, as well
as METEOR (Denkowski and Lavie, 2011) on the word level. For METEOR,
we used the language-independent setting for Japanese and Finnish, and thelanguage-dependent settings for the remaining languages.
Table 2 shows the results of the evaluation. It can be seen that in general,character-based translation with all of the proposed alignment improvements
greatly exceeds character-based translation using the IBM models, conﬁrming
the hypothesis that substring-based information is necessary for accurate alignments. In general, the accuracy of character-based translation is comparable orslightly inferior to that of word-based translation. The evaluation of characterbased BLEU shows that character-based translation is superior, comparable,
or inferior depending on the language pair, word-based METEOR shows thatcharacter-based translation is comparable or inferior, and word-based BLEU
shows that character-based translation is inferior.
9

http://phontron.com/pialign/
This setup was chosen to minimize the eﬀect of the tuning criterion on the comparison
between the baseline and the proposed system, although it does imply that we must haveaccess to tokenized data for the development set.
11 We also performed experiments in which we incorporated a word-based language modelin character-based translation, but found that this consistently gave neutral to negative
results, a similar ﬁnding to that of Vilar et al (2007). We suspect that this is due to the factthat word-based language models assign a sudden, large penalty when a word completes,
hurting decoding. In addition, the modeling of unknown words is not trivial, and while we
provided a ﬁxed penalty for each unknown word (tuned using MERT), a more sophisticatedunknown word model is probably necessary.
10Substring-based Machine Translation

19

Table 2 Translation results for word-based BLEU (wBLEU), character-based BLEU
(cBLEU), and METEOR for the GIZA++ and ITG models for word and character-basedtranslation, with bold numbers indicating a statistically insigniﬁcant diﬀerence from thebest system according to the bootstrap resampling method at p = 0.05.
de-en

GIZA-word
ITG-word
GIZA-char
ITG-char

en-de

wBLEU

cBLEU

METEOR

wBLEU

cBLEU

METEOR

24.58
23.87
08.05
21.79

64.28
64.89
45.01
64.47

30.43
30.71
15.35
30.12

17.94
17.47
06.17
15.35

62.71
63.18
41.04
61.95

37.88
37.79
19.90
35.45

ﬁ-en

GIZA-word
ITG-word
GIZA-char
ITG-char

en-ﬁ

wBLEU

cBLEU

METEOR

wBLEU

cBLEU

METEOR

20.41
20.83
06.91
18.38

60.01
61.04
41.62
62.44

27.89
28.46
14.39
28.94

13.22
13.12
04.58
12.14

58.50
59.27
35.09
59.02

27.03
27.09
11.76
25.31

fr-en

GIZA-word
ITG-word
GIZA-char
ITG-char

en-fr

wBLEU

cBLEU

METEOR

wBLEU

cBLEU

METEOR

30.23
29.92
11.05
26.70

68.79
68.64
48.23
66.76

34.20
34.29
17.80
32.47

32.19
31.66
10.31
27.74

69.20
69.61
42.84
67.44

52.39
51.98
25.06
48.56

ja-en

GIZA-word
ITG-word
GIZA-char
ITG-char

en-ja

wBLEU

cBLEU

METEOR

wBLEU

cBLEU

METEOR

17.95
17.14
09.46
15.84

56.47
56.60
49.02
58.41

24.70
24.89
18.34
24.58

20.79
20.26
01.48
17.90

27.01
28.34
00.72
28.46

38.41
38.34
06.67
35.71

For translation into English, character-based translation achieves higher
relative accuracy compared to word-based translation on Japanese and Finnish
input, followed by German, and ﬁnally French. This is notable in that it conﬁrms the fact that character-based translation is performing well on languages
that have long words or ambiguous boundaries, and less well on language pairs
with a relatively strong one-to-one correspondence between words in both languages.

6.3 Eﬀect of Improvements to the Alignment Method
This section compares the translation accuracy for character-based translation
using the ITG model with and without the proposed improvements of substring
co-occurrence priors and look-ahead parsing as described in Sections 4 and 5.

20

Graham Neubig et al.

Table 3 METEOR scores for alignment with and without look-ahead and co-occurrence
priors.

ITG +cooc +look
ITG +cooc -look
ITG -cooc +look
ITG -cooc -look

ﬁ-en

en-ﬁ

ja-en

en-ja

28.94
28.51
28.65
27.45

25.31
24.24
24.49
23.30

24.58
24.32
24.36
23.57

35.71
35.74
35.05
34.50

Table 4 An adequacy evaluation of word- and character-based MT (0–5 scale).

ITG-word
ITG-char

ﬁ-en

ja-en

2.851
2.826

2.085
2.154

METEOR scores for experiments translating Japanese and Finnish are
shown in Table 3.12 It can be seen that the co-occurrence prior probability provides gains in all cases, indicating that the using substring statistics over thewhole corpus are providing eﬀective prior knowledge to the ITG aligner. The
introduced look-ahead probabilities improve accuracy signiﬁcantly when substring co-occurrence counts are not used, but only slightly when co-occurrence
counts are used. More importantly, they allow for more aggressive beam pruning, increasing sampling speed from 1.3 sent/s to 2.5 sent/s on the Finnish
task, and 6.8 sent/s to 11.6 sent/s on the Japanese task.

6.4 Qualitative Evaluation
This section presents the results of a subjective evaluation of Japanese–English
and Finnish–English translations. In the evaluation, two raters evaluated 100
sentences each, assigning an adequacy score of 0–5 based on how well thetranslation conveys the information contained in the reference translation. The
raters were asked to rate on shorter sentences of 8–16 English words to easerating and interpretation. The results of this evaluation are shown in Table 4.
It can be seen that the results are comparable, with no signiﬁcant diﬀerencein average scores for either language pair.
A breakdown of the types of sentences for which character-based translation was given a score of at least two points more than word-based is shownin Table 5. It can be seen that character-based translation is, in fact, properly
handling a number of sparsity phenomena. On the other hand, word-basedtranslation was generally stronger with reordering and lexical choice of morecommon words.
12

Character-based BLEU and word-based BLEU showed similar relative gains.

Substring-based Machine Translation

21

Table 5 The major gains of character-based translation, source-side unknown words (Src),
target-side unknown words (Trg), and rare words (Rare). “#” indicates the total number ofoccurrences of each gain.
Type#

Reference

ITG-Word

ITG-Char

Src
Trg
Rare

13
5
5

directive on equality
yoshiwara-juku stationworld health organisationtasa-arvodirektiivi
yoshiwara no eki
world healthequality directive
yoshiwara-juku stationworld health organisation

Table 6 The number of phrases that were the same, diﬀerent but of equal quality, or
subjectively better translations in one of the two models.

Same phrase
Equal quality
ITG-char better
ITG-word better

ﬁ-en

ja-en

220
209
67
35

215
217
96
69

6.5 Phrases Used in Translation
This section presents an analysis of the phrases used in the translation of
50 sentences using word- and character-based ITG alignment for the Finnish–
English and Japanese–English tasks. First, Table 6 shows the number of phrases
where the phrase used by one of the two systems was subjectively better thanthe phrase used by the other system. It can be seen that there are a greaternumber of accurate translations at the phrase level for the character-based
system than for the word-based system across both languages.
In order to examine the types of phrases where one of the two systems ismore accurate than the other, Table 7 and Table 8 provide more detailed breakdowns by type of the mistranslated phrases used by each of the models for
Finnish–English and Japanese–English translation, respectively. It can be seenthat character-based translation naturally handles a number of phenomena
due to unknown words that are not handled by word-based systems, such as
those requiring transliteration, decompounding, and division of morphologicalcomponents. It should also be noted that this process is not perfect; there are
a number of cases where character-based translation splits or transliterates
words that would be more accurately translated as a whole, although thetotal number of correctly translated compounds and inﬂected words is morethan twice the number of incorrectly translated ones.
With regards to Finnish–English, it is interesting to note that characterbased translation also succeeded in discovering a number of inﬂectional suﬃxes
that have a clear grammatical function in the language (Karlsson, 1999). Examples of the most common sub-word units used in translation are shown in
Table 9. It can be seen that all but one have a clear grammatical functionin Finnish. The only exception “s” is used in the transliteration of unknown
words, as well as part of some morphological paradigms (similarly to “e”).

22Graham Neubig et al.

Table 7 A phrase-by-phrase analysis of gains and losses for Finnish–English translation
categorized by errors due to misalignment (Mis), conjugation (Conj.), deletion of a word
(Del.), insertion of a word (Ins.), compound words (Comp.), and lexical choice (Lex.). “#”indicates the total number of instances of each class.
ITG-char Better
#

Type

19

Mis.

18

Conj.

12

Del.

12

Comp.

10

Ins.

8

Lex.

#

Type

19

Del.

15

Ins.

6

Lex.

5

Mis.

4

Conj.

Source

ITG-charitsenäisilleindependent (pos./all.)perustuslaillisempi
constitution (comp.)
kuuluisibelong (cond.)
yleismietintöä
the general report
myös
also
pelkojenfears/emotions

ITG-word

independent foreconomic reform

constitution more

perustuslaillisempi

would include

would

the general report ,yleismietintöä

also

will also befears

emotions

ITG-word Better
Source (Case)itsellemmeourselves (all.)haluani would like tojoin/alreadyon vastattava
is answer
vertailuanalyysiä
benchmarking

ITG-char

ITG-wordspace

ourselves

i would like to makei would like toalreadyinmust beis answer

comparative analysis

benchmarking

This demonstrates that despite using no sort of explicit morphological knowledge, character-based translation is able to handle, to some extent, the morecommon morphological paradigms in morphologically rich languages.
One signiﬁcant area for improvement in the character-based model is thatit has a tendency to create alignments of actual content words on the sourceside to the white space character on the target side, eﬀectively deleting content
words. While deleted words are a problem in the word-based model as well,
the problem is more prevalent in the character-based model, so it will be worth
examining the possibilities of giving space characters a special status in thetranslation model in the future.
Finally, we note that the character-based model helps not only with unknown words, but also words that do exist, but are misaligned by the wordbased model because they are rare, or do not have a consistent translation.
In fact, this was the single most common error category for Finnish–English,
and a signiﬁcant portion of the Japanese–English errors. This indicates that
simply applying character-based methods to process unknown words will not
be suﬃcient to overcome the sparsity issues of the word-based model.

Substring-based Machine Translation

23

Table 8 A phrase-by-phrase analysis of gains and losses for Japanese–English translation
categorized by errors due to transliteration (Tran.), insertion of a word (Ins.), deletion of aword (Del.), insertion of a word (Ins.), misalignment (Mis.), lexical choice (Lex.), compoundwords (Comp.), or partial transliteration (Part.). “#” indicates the total number of instancesof each class.

ITG-char Better
#

Type

38

Tran.

19

Ins.

19

Del.

17

Mis.

2

Lex.

2

Comp.

#

Type

28

Del.

11

Ins.

11

Tran.

10

Mis.

5

Part.

2

Lex.

Source

ITG-char

希玄
kigen
半年間
six months
病のため
due to illness
を求めて
seeking
俗lay/commonly called
顔洗い
face washing

ITG-word

kigen

希玄

half year

six months between

due to his illness

illness

seekingthelaycommonly called

face washing

顔洗い

ITG-word Better
Sourceも用いた。
was also used .
招請
invited無常
vanity書かれたwritten
大佛
osaragiでin/andITG-char

ITG-word.

was also used .

invited continvitedmujo

vanitythewrittenososaragiandinTable 9 Common Finnish sub-word phrases along with their grammatical function.
String

#

n
a
i
t
sta
e
lle
s
ä
in
ssa

564
467
307
241
235
156
134
133
121
114
94

Grammatical Function
genitive (“of X”)
partitive (“some X”)
plural, non-nominative (“Xs”)
plural, nominative (“Xs”)
elative (“out of X”)
similar to “e” in “played”
allative (“onto X”)
partitive (“some X”)
plural, genitive (“of Xs”)
inessive (“in X”)

24Graham Neubig et al.

Table 10 Translation results in word-based BLEU (wBLEU), character-based BLEU
(cBLEU), and METEOR for the ITG model for word- or character-based input and output.
Bold indicates a statistically insigniﬁcant diﬀerence from the best system p = 0.05.
ﬁ-en

word → wordchar → charword → char
char → word

en-ﬁ

wBLEU

cBLEU

METEOR

wBLEU

cBLEU

METEOR

20.58
17.97
16.48
19.44

60.86
61.30
57.23
61.94

28.47
28.71
25.73
29.09

13.06
11.92
11.18
10.78

60.14
58.86
58.41
56.49

27.20
25.09
24.70
24.85

ja-en

word → wordchar → charword → char
char → word

en-ja

wBLEU

cBLEU

METEOR

wBLEU

cBLEU

METEOR

17.07
15.41
14.98
15.65

56.52
58.06
55.64
56.62

24.73
24.57
23.37
24.42

19.96
17.59
19.08
17.60

28.15
28.51
27.35
28.72

38.26
35.74
37.08
36.04

6.6 Character-to-Word and Word-to-Character Translation
Up until now, we have mainly considered the traditional combination of translation from words to words, and translation from characters to characters.
However, it is easy to imagine the translation from word strings on the sourceside to character strings on the target side, or vice-versa. In order to examine
the eﬀect of character-to-word or word-to-character translation, we performed
additional experiments where only the source or target side was divided into
characters, and the other parts of the text were left as words.
The results of these experiments for Finnish–English and Japanese–English
translation are shown in Table 10.13 From this table, it can be seen that there isno clear strategy for obtaining the highest accuracy across all language pairs.
In general it can be seen that the largest positive eﬀect of character-basedtranslation can be obtained by dividing Japanese or Finnish on the sourceside. This is a reasonable result given the features of the languages, as wellas our previous analysis, which showed that the largest number of gains fromcharacter-based translation were for unknown words on the source side.

6.7 Eﬀect of the Reordering Limit
Finally we examine the eﬀect of the reordering limit on word- and characterbased translation for Finnish and Japanese to and from English. The reordering limit is a hard constraint on the length of reorderings allowed by phrasebased translation that is essential for producing translations eﬃciently (Koehn
13 These numbers were produced with a diﬀerent version of Moses than the numbers inprevious sections, so should not be directly compared.

Substring-based Machine Translation

25

Fig. 5 Accuracy for four language pairs at each reordering limit

et al, 2005). All previous experiments used Moses’ default reordering limit of
6 elements, which is often a reasonable limit for word-based translation, especially for similar language pairs. However, for character-based translation,a limit of 6 characters will often only translate into the reordering of a single
word (or less). Thus, it could be expected that the eﬀect of diﬀerent reordering
limits will have diﬀerent eﬀects on word- and character-based translation.
In order to examine the eﬀect of the reordering limit, in Figure 5 we show
results for ITG-word and ITG-char over four language pairs with reordering
limits of 0, 6, 12, 18, and 24. First, examining the results for word-basedtranslation, we can see that a reordering limit of 6 is ideal for all language
pairs except Japanese–English, which achieves the highest accuracy with areordering limit of 12.
On the other hand, the results are much less consistent for character-basedtranslation. For translation to or from Japanese, a large reordering limit generally helps character-based translation, with limits of 18 and 24 achieving
ideal results for Japanese–English and English–Japanese, respectively. This isa somewhat expected result, as we require a larger reordering limit to handle the same types of reordering that may be covered by the character-basedmodel. However, for English–Finnish translation there is no clear improvement
by increasing the reordering limit, and for Finnish–English translation accuracy actually decreases signiﬁcantly for any limit over 0. This indicates thatthe search space for character-based translation is too large, and the lexicalized
phrase-based reordering models are too weak to ﬁnd an appropriate reordering
within this search space. Given this, it is likely that improved methods of decoding or constraining the search space within the character-based translation
framework could further improve translation accuracy quite signiﬁcantly.

26

Graham Neubig et al.

7 Conclusion
This paper demonstrated that given improvements to alignment, characterbased translation is able to act as a uniﬁed framework for handling a numberof diﬃcult problems in translation: morphology, compound words, transliteration, and word segmentation. It also presented two advances to many-to-manyalignment methods that allow them to be run on much longer sentences, andimprove accuracy through substring-based prior probabilities. However, while
this is a ﬁrst step towards moving beyond the concept of words in MT, there
are still a number of remaining challenges.
One of the major challenges for the future is the development of eﬃcient
decoding methods for character-based translation models. As shown in theanalysis of phrase quality in the system, the character-based model is able
to produce better translations on the phrase level, but nevertheless achieves
results that are approximately equal to those of the word-based systems. The
major reason for this gap is that the word-based model tends to be better atreordering, as it is able to treat whole words as single units, which gives it
both more freedom to handle reorderings over long distances and a more constrained search space that only considers more reasonable reorderings. Given
more eﬀective and eﬃcient decoding methods, it is likely that we will be able
to further close this gap in reordering quality, resulting in a clear advantageof the character-based models over word-based models.
In addition, there are still signiﬁcant improvements that could be made toalignment speed to scale to longer sentences. This can probably be achieved
through methods such as the heuristic span pruning of Haghighi et al (2009)or sentence splitting of Vilar et al (2007).
Finally, an interesting future direction is the consideration of discontiguous
spans in character-based alignment. As noted in Figure 1, the proposed model
was able to capture a rudimentary concept agreement by learning phrases thatcombine the plural suﬃx of nouns with the plural form of a verb. Learning
discontiguous spans (possibly with a method similar to that of Levenberg et al(2012)) could further allow for the entirely unsupervised learning of morphological agreement, even when there are words intervening between the words
that must agree.

References
Abouelhoda MI, Kurtz S, Ohlebusch E (2004) Replacing suﬃx trees withenhanced suﬃx arrays. Journal of Discrete Algorithms 2(1):53–86
Al-Onaizan Y, Knight K (2002) Translating named entities using monolingual and bilingual resources. In: 40th Annual Meeting of the Association
for Computational Linguistics, Proceedings of the Conference, Philadelphia,
PA, USA, pp 400–408
Bai MH, Chen KJ, Chang JS (2008) Improving word alignment by adjusting
Chinese word segmentation. In: IJCNLP 2008, Proceedings of the 3rd In-

Substring-based Machine Translation27

ternational Joint Conference on Natural Language Processing, Hyderabad,
India, pp 249–256
Blunsom P, Cohn T (2010) Inducing synchronous grammars with slice sampling. In: Human Language Technologies: The 2010 Annual Conference of
the North American Chapter of the Association for Computational Linguistics, Proceedings of the Main Conference, Los Angeles, California, pp
238–241
Blunsom P, Cohn T, Dyer C, Osborne M (2009) A Gibbs sampler for phrasal
synchronous grammar induction. In: ACL-IJCNLP 2009, Joint Conferenceof the 47th Annual Meeting of the Association for Computational Linguistics
and 4th International Joint Conference on Natural Language Processing of
the AFNLP, Proceedings of the Conference, Suntec, Singapore, pp 782–790
Bojar O (2007) English-to-Czech factored machine translation. In: ACL 2007:
Proceedings of the Second Workshop on Statistical Machine Translation,
Prague, Czech Republic, pp 232–239
Brown PF, Della-Pietra VJ, Della-Pietra SA, Mercer RL (1993) The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics 19:263–312
Brown RD (2002) Corpus-driven splitting of compound words. In: TMI-2002
Conference: Proceedings of the 9th International Conference on Theoreticaland Methodological issues in Machine Translation, Keihanna, Japan, pp
12–21
Chang PC, Galley M, Manning CD (2008) Optimizing Chinese word segmentation for machine translation performance. In: ACL-08: HLT: Third
Workshop on Statistical Machine Translation, Proceedings of the Workshop,
Columbus, Ohio, USA, pp 224–232
Chomsky N (1956) Three models for the description of language. IRE Transactions on Information Theory 2(3):113–124
Chu C, Nakazawa T, Kawahara D, Kurohashi S (2012) Exploiting shared
Chinese characters in Chinese word segmentation optimization for ChineseJapanese machine translation. In: EAMT 2012, Proceedings of the 16th
Annual Conference of the European Association for Machine Translation,
Trento, Italy, pp 35–42
Chung T, Gildea D (2009) Unsupervised tokenization for machine translation.
In: EMNLP 2009: Proceedings of the 2009 Conference on Empirical Methods
in Natural Language Processing, Singapore, pp 718–726
Corston-Oliver S, Gamon M (2004) Normalizing German and English inﬂectional morphology to improve statistical word alignment. In: Machine Translation: From Real Users to Research, 6th Conference of the Association for
Machine Translation in the Americas, AMTA 2004, Washington, DC, USA,pp 48–57
Cromières F (2006) Sub-sentential alignment using substring co-occurrence
counts. In: COLING · ACL 2006, 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Student Research Workshop, Sydney, Australia, pp 13–18

28

Graham Neubig et al.

DeNero J, Bouchard-Côté A, Klein D (2008) Sampling alignment structure
under a Bayesian translation model. In: EMNLP 2008: 2008 Conferenceon Empirical Methods in Natural Language Processing, Proceedings of theConference, Honolulu, Hawaii, USA, pp 314–323
Denkowski M, Lavie A (2011) Meteor 1.3: Automatic Metric for Reliable Optimization and Evaluation of Machine Translation Systems. In: Proceedings of
the 6th Workshop on Statistical Machine Translation (WMT), Edinburgh,
Scotland, UK, pp 85–91
Denoual E, Lepage Y (2005) BLEU in characters: towards automatic MT
evaluation in languages without word delimiters. In: Proceedings of the 2nd
International Joint Conference on Natural Language Processing, IJCNLP05, Jeju Island, Korea, pp 81–86
Finch A, Sumita E (2007) Phrase-based machine transliteration. In: Proceedings of the Workshop on Technologies and Corpora for Asia-Paciﬁc Speech
Translation (TCAST), Hyderabad, India, pp 13–18
Goldwater S, McClosky D (2005) Improving statistical MT through morphological analysis. In: HLT/EMNLP 2005: Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, Proceedings of the Conference, Vancouver, British Columbia, Canada,
pp 676–683
Haghighi A, Blitzer J, DeNero J, Klein D (2009) Better word alignments withsupervised ITG models. In: ACL-IJCNLP 2009, Joint Conference of the
47th Annual Meeting of the Association for Computational Linguistics and4th International Joint Conference on Natural Language Processing of the
AFNLP, Proceedings of the Conference, Suntec, Singapore, pp 923–931
Jiang J, Ahmed Z, Carson-Berndsen J, Cahill P, Way A (2011) Phonetic
representation-based speech translation. Proceedings of Machine Translation Summit XIII, Xiamen, China, pp 81–88
Karlsson F (1999) Finnish: An Essential Grammar. Routledge: London.
Klein D, Manning CD (2003) A* parsing: fast exact Viterbi parse selection.
In: HLT-NAACL 2003: conference combining Human Language Technology
conference series and the North American Chapter of the Association for
Computational Linguistics conference series, Edmonton, Canada, pp 40–47
Kneser R, Ney H (1995) Improved backing-oﬀ for M-gram language modelling.
In: International Conference on Acoustics, Speech, and Signal Processing(ICASSP), vol. 1, Detroit, Michigan, USA, pp 181–184
Knight K, Graehl J (1998) Machine transliteration. Computational Linguistics
24(4):599–612
Koehn P (2005) Europarl: A parallel corpus for statistical machine translation. In: MT Summit X: The Tenth Machine Translation Summit, Phuket,
Thailand, pp 79–86
Koehn P, Axelrod A, Mayne AB, Callison-Burch C, Osborne M, Talbot D(2005) Edinburgh system description for the 2005 IWSLT speech translation evaluation. In: International Workshop on Spoken Language Translation: Evaluation Campaign on Spoken Language Translation [IWSLT 2005],
Pittsburgh, USA, 8pp [no page numbers]

Substring-based Machine Translation

29

Koehn P, Hoang H, Birch A, Callison-Burch C, Federico M, Bertoldi N, Cowan
B, Shen W, Moran C, Zens R, Dyer C, Bojar O, Constantin A, Herbst E(2007) Moses: Open source toolkit for statistical machine translation. In:
ACL 2007: proceedings of demo and poster sessions, Prague, Czech Republic, pp 177–180
Koehn P, Och FJ, Marcu D (2003) Statistical phrase-based translation. In:
HLT-NAACL 2003: conference combining Human Language Technology
conference series and the North American Chapter of the Association for
Computational Linguistics conference series, Edmonton, Canada, pp 48–54
Kondrak G, Marcu D, Knight K (2003) Cognates can improve statistical translation models. In: HLT-NAACL 2003: conference combining Human Language Technology conference series and the North American Chapter ofthe Association for Computational Linguistics conference series, Edmonton,
Canada, pp 46–48
Lee YS (2004) Morphological analysis for statistical machine translation. In:
HLT-NAACL 2004: Human Language Technology Conference of the North
American Chapter of the Association for Computational Linguistics, Proceedings of the Main Conference, Boston, Massachusetts, USA, pp 57–60
Levenberg A, Dyer C, Blunsom P (2012) A Bayesian model for learning SCFGs
with discontiguous rules. In: Proceedings of the 2012 Joint Conference on
Empirical Methods in Natural Language Processing and Computational
Natural Language Learning (EMNLP-CoNLL), Jeju Island, Korea, pp 223–
232
Li H, Zhang M, Su J (2004) A joint source-channel model for machine transliteration. In: Proceedings of the 42nd Annual Meeting of the Association for
Computational Linguistics (ACL), Barcelona, Spain, pp 159–166
Li M, Zong C, Ng HT (2011) Automatic evaluation of Chinese translation
output: Word-level or character-level? In: Proceedings of the 49th Annual
Meeting of the Association for Computational Linguistics (ACL), Portland,
Oregon, pp 159–164
Liang P, Taskar B, Klein D (2006) Alignment by agreement. In: Proceedings ofthe 2006 Human Language Technology Conference of the North American
Chapter of the Association for Computational Linguistics (HLT-NAACL),
Montreal, Canada, pp 104–111
Liu C, Ng HT (2012) Character-level machine translation evaluation for languages with ambiguous word boundaries. In: [ACL 2012] Proceedings of
the 50th Annual Meeting of the Association for Computational Linguistics,
Jeju, Republic of Korea, pp 921–929
Macherey K, Dai A, Talbot D, Popat A, Och F (2011) Language-independent
compound splitting with morphological operations. In: ACL-HLT 2011: Proceedings of the 49th Annual Meeting of the Association for Computational
Linguistics, Portland, Oregon, pp 1395–1404
Marcu D, Wong W (2002) A phrase-based, joint probability model for statistical machine translation. In: Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing, Philadelphia, PA, USA, pp
133–139

30

Graham Neubig et al.

Nakov P, Tiedemann J (2012) Combining word-level and character-level models for machine translation between closely-related languages. In: [ACL 2012]
Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics, Jeju, Republic of Korea, pp 301–305
Naradowsky J, Toutanova K (2011) Unsupervised bilingual morpheme segmentation and alignment with context-rich hidden semi-Markov models. In:
ACL-HLT 2011: Proceedings of the 49th Annual Meeting of the Association
for Computational Linguistics, Portland, Oregon, pp 895–904
Neubig G (2011) The Kyoto free translation task. http://www.phontron.
com/kftt
Neubig G, Watanabe T, Mori S, Kawahara T (2012) Machine translation without words through substring alignment. In: : [ACL 2012] Proceedings of the50th Annual Meeting of the Association for Computational Linguistics, Jeju,
Republic of Korea, pp 165–174
Neubig G, Watanabe T, Sumita E, Mori S, Kawahara T (2011) An unsupervised model for joint phrase alignment and extraction. In: ACL-HLT 2011:
Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, Portland, Oregon, pp 632–641
Nguyen T, Vogel S, Smith NA (2010) Nonparametric word segmentation formachine translation. In: Coling 2010, 23rd International Conference on Computational Linguistics, Proceedings of the Conference, Beijing, China, pp
815–823
Nießen S, Ney H (2000) Improving SMT quality with morpho-syntactic analysis. In: The 18th International Conference on Computational Linguistics,
COLING 2000 in Europe, Proceedings of the Conference, Saarbrücken, Germany, pp 1081–1085
Och, FJ (2003) Minimum error rate training in statistical machine translation.
In: ACL-2003: 41st Annual meeting of the Association for Computational
Linguistics, Sapporo, Japan, pp 160–167
Och FJ, Ney H (2003) A systematic comparison of various statistical alignment
models. Computational Linguistics 29(1):19–51
Papineni K, Roukos S, Ward T, Zhu WJ (2002) BLEU: a method for automatic evaluation of machine translation. In: 40th Annual Meeting of the
Association for Computational Linguistics, Proceedings of the Conference,
Philadelphia, PA, USA, pp 311–318
Saers M, Nivre J, Wu D (2009) Learning stochastic bracketing inversion transduction grammars with a cubic time biparsing algorithm. In: IWPT-09:
Proceedings of the 11th International Conference on Parsing Technologies,
Paris, France, pp. 29–32
Snyder B, Barzilay R (2008) Unsupervised multilingual learning for morphological segmentation. In: ACL-08: HLT, 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Proceedings of the Conference, Columbus, Ohio, USA, pp 737–745
Sornlertlamvanich V, Mokarat C, Isahara H (2008) Thai-lao machine translation based on phoneme transfer. In: Proceedings of the 14th Annual Meetingof the Association for Natural Language Processing, Tokyo, Japan, pp 65–68

Substring-based Machine Translation

31

Subotin M (2011) An exponential translation model for target language morphology. In: ACL-HLT 2011: Proceedings of the 49th Annual Meeting of the
Association for Computational Linguistics, Portland, Oregon, pp 230–238
Talbot D, Osborne M (2006) Modelling lexical redundancy for machine translation. In: COLING · ACL 2006, 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, Sydney, Australia, pp
969–976
Tiedemann J (2009) Character-based PSMT for closely related languages. In:
EAMT-2009: Proceedings of the 13th Annual Conference of the European
Association for Machine Translation, Barcelona, Spain, pp 12–19
Tiedemann J (2012) Character-based pivot translation for under-resourced
languages and domains. In: [EACL 2012] Proceedings of the 13th Conferenceof the European Chapter of the Association for Computational Linguistics,
Avignon, France, pp 141–151
Vilar D, Peter JT, Ney H (2007) Can we translate letters? In: ACL 2007:
Proceedings of the Second Workshop on Statistical Machine Translation,
Prague, Czech Republic, pp 33–39
Vogel S, Ney H, Tillmann C (1996) HMM-based word alignment in statisticaltranslation. In: COLING-96: The 16th International Conference on Computational Linguistics, Proceedings, Copenhagen, Denmark, pp 836–841
Wang Y, Uchimoto K, Kazama J, Kruengkrai C, Torisawa K (2010) Adapting
Chinese word segmentation for machine translation based on short units.
In: LREC 2010: proceedings of the seventh international conference on Language Resources and Evaluation, La Valetta, Malta, pp 1758–1764
Wu D (1997) Stochastic inversion transduction grammars and bilingual parsingof parallel corpora. Computational Linguistics 23(3):377–403
Xu J, Zens R, Ney H (2004) Do we need Chinese word segmentation for statistical machine translation? In: Proceedings of the 3rd SIGHAN workshop
on Chinese language processing, Barcelona, Spain, pp 122–128
Zhang H, Gildea D (2005) Stochastic lexicalized inversion transduction grammar for alignment. In: ACL-05: 43rd Annual Meeting of the Association for
Computational Linguistics Ann Arbor, Michigan, USA, pp 475–482
Zhang H, Quirk C, Moore RC, Gildea D (2008a) Bayesian learning of noncompositional phrases with synchronous parsing. In: ACL-08: HLT, 46th
Annual Meeting of the Association for Computational Linguistics: Human
Language Technologies, Proceedings of the Conference, Columbus, Ohio,
USA, pp 97–105
Zhang R, Yasuda K, Sumita E (2008b) Improved statistical machine translation by multiple Chinese word segmentation. In: ACL-08: HLT: Third
Workshop on Statistical Machine Translation, Proceedings of the Workshop,
Columbus, Ohio, USA, pp 216–223