Electronic Preprint for Journal of Information Processing Vol.20 No.2

Regular Paper

Joint Phrase Alignment and Extraction
for Statistical Machine Translation
Graham Neubig1,2,a)Taro Watanabe2 Eiichiro Sumita2
Tatsuya Kawahara1

Shinsuke Mori1

Received: May 24, 2011, Accepted: December 16, 2011

Abstract: The phrase table, a scored list of bilingual phrases, lies at the center of phrase-based machine translation
systems. We present a method to directly learn this phrase table from a parallel corpus of sentences that are not aligned
at the word level. The key contribution of this work is that while previous methods have generally only modeled phrases
at one level of granularity, in the proposed method phrases of many granularities are included directly in the model.
This allows for the direct learning of a phrase table that achieves competitive accuracy without the complicated multistep process of word alignment and phrase extraction that is used in previous research. The model is achieved throughthe use of non-parametric Bayesian methods and inversion transduction grammars (ITGs), a variety of synchronouscontext-free grammars (SCFGs). Experiments on several language pairs demonstrate that the proposed model matches
the accuracy of the more traditional two-step word alignment/phrase extraction approach while reducing its phrase
table to a fraction of its original size.
Keywords: statistical machine translation, phrase alignment, non-parametric Bayesian statistics, inversion transduction grammars

1. Introduction
Statistical machine translation (SMT) has seen great improvements over the past decade thanks largely to the introduction ofphrase-based translation, which helps resolve lexical ambiguity
and short-distance reordering by translating multi-word phrases
as single chunks. The most important element of phrase-based
SMT systems is the “phrase table,” a scored list of bilingualphrase pairs that are translations of each other. This phrase table
is generated from a parallel corpus of translated sentences that are
not aligned at the word or phrase level.
Traditional systems construct phrase tables by going througha two-step pipeline. The first step consists of finding alignments
between words or minimal phrases in both sentences, while thesecond step extracts an expanded phrase table from these alignments through heuristic combination of words or minimal phrases
into longer units. The ability to use both short single-word units
and longer phrases is one of the major reasons why phrasebased translation achieves superior results to word-based methods. However, it has been shown in previous research [13] that
this two step approach results in word alignments that are not optimal for the final task of generating phrase tables that are usedin translation. In addition, exhaustively extracted phrase tables
are often unnecessarily large, which results in an increase in theamount of time and memory required to run machine translation
1
2
a)Graduate School of Informatics, Kyoto University, Kyoto 606–8501,
Japan
National Institute of Information and Communications Technology,
Keihanna Science City, Kyoto 619–2089, Japanneubig@ar.media.kyoto-u.ac.jp

c 2012 Information Processing Society of Japansystems.
In this paper, we propose an approach that is able to reduce
the two steps of alignment and extraction into a single step by including phrases of multiple granularities in a probabilistic alignment model. The model is based on inversion transduction grammars (ITGs [34]), a variety of synchronous context free grammars (SCFGs). ITGs allow for eﬃcient word or phrase alignment [2], [5], [35] through the use of bilingual chart parsing, similar to parsing algorithms used widely for the parsing of monolingual CFGs.
In contrast to previous approaches, which generally only attempt to model word (or minimal phrase) alignments, the proposed method models phrases at multiple levels of granularity
through a novel recursive formulation, where larger phrase pairs
are probabilistically constructed from two smaller phrase pairs.
The model uses methods from non-parametric Bayesian statistics, which favor simpler models, preventing the over-fitting that
occurs in some previous alignment approaches [22].
Using this model, we create phrase tables and perform machinetranslation experiments over four language pairs. We observe thatthe proposed hierarchical model is able to meet or exceed results
attained by the traditional combination of word alignment andheuristic phrase extraction with significantly smaller phrase tablesize. We also find that in contrast, previously proposed ITG-based
phrase alignment approaches are not able to achieve competitive
accuracy without heuristic phrase extraction and the accompanying increase in phrase table size.

Electronic Preprint for Journal of Information Processing Vol.20 No.2

2. Phrase-Based Statistical Machine Translation
Machine translation is the process of automatically translating a sentence F in a source (foreign) language, into an equivalent sentence E in the target (English) language. Many modern
machine translation (MT) systems utilize phrase-based MT [20]techniques, which break F into phrases of one or more words,
each of which is individually translated and reordered to form E.
An example of a phrase-based translation is shown in Fig. 1. Itshould be noted that in addition to F and E, there is a string A
of alignment spans that indicates which parts of F were translated into which parts of E. Each element of A takes the form{[ae1 , ae2 ], [a f 1 , a f 2 ]} indicating a single pair of phrases in thesource and target sentences. The variables ae1 and ae2 indicate
the position of the first and last words of the target phrase, whilea f 1 and a f 2 indicate the position of the first and last words of thesource phrase respectively.
For any particular source sentence F there are many possible
translations, some more natural or semantically correct than others. Statistical machine translation (SMT) attempts to resolve thisambiguity by creating a statistical model for the target sentence
and alignment given the source sentence, and finding the target
sentence that maximizes this probability:Ê = argmaxP(E, A|F).

(1)

E

The predominant paradigm for calculating this probability is
the log-linear model of Ref. [27]. This model defines the logarithm of the translation probability as a linear combination of aset of feature functions φ1 , . . . , φI over E, F, and A, weighted
with weights λ1 , . . . , λI
log P(E, A|F) =Iλi φi (E, F, A).

(2)

i=1

This formulation allows arbitrary features of E, F, and A to be
used in determining the translation probabilities. Commonly usedfeature functions include log language model probabilities and reordering probabilities. The language model probabilities are defined over E, and attempt to measure the fluency of the generated
sentence. The reordering probabilities are defined over A, andattempt to ensure that the word order is appropriate.
However, the features that most directly aﬀect the translation
quality are those that belong to the phrase table. As shown in
the example in Fig. 2, the phrase table is a collection of phrase
pairs, consisting of equivalent source and target language phrases( f and e respectively). Each phrase pair is additionally scoredwith several feature functions, which will be explained in more

Fig. 1 The target sentence F, source sentence E, and alignment A.

c 2012 Information Processing Society of Japandetail in Section 6. These feature functions are used to provide
an indication of the reliability or frequency of each phrase pair,and can be learned from a corpus consisting of translated pairs ofsentences in the source and target languages.

3. Alignment Using Inversion Transduction
Grammars
The first step in creating a phrase table from a sentence-aligned
parallel corpus is alignment, the process of finding which words
or phrases in the source and target sides of the training data correspond to each other. Following the definitions presented in theprevious section, this means that we are given a parallel training
corpus consisting of F = F1 , . . . , Fn and E = E1 , . . . , En , andwe must find the corresponding alignments A = A1 , . . . , An . One
framework for learning these alignments that has been used in a
number of recent works [2], [5], [35] is the inversion transduction
grammar (ITG) [34].
ITGs are a form of context-free grammar (CFG) in Chomsky
normal form [7], defined over two languages instead of one. Like
normal CFGs, ITGs have non-terminal, pre-terminal, and terminal symbols, but each node generates bilingual phrase pairs e, f instead of the single monolingual phrases generated by normal
CFGs. The most important characteristic of ITGs is the nonterminal symbols, which can be either “straight” or “inverted.”
If a non-terminal node’s left and right child nodes have generated
the phrase pairs e1 , f 1  and e2 , f 2  respectively, in the case of
the straight non-terminals, these will be concatenated in order ase1 e2 , f 1 f 2 , while in the case of inverted nodes, the phrases off are concatenated in inverted reverse order as e1 e2 , f 2 f 1 . An
example of straight and inverted nodes is shown in Fig. 3.
Like probabilistic CFGs, which assign probabilities to eachgenerative grammar rule over monolingual phrases, ITGs can also
be assigned a generative probability distribution over bilingualphrase pairs. The traditional ITG generative probability for a particular phrase pair P f lat (e, f ; θ x , θt ) is parameterized by a phrase
table θt (which specifies a probability distribution over terminal
symbols) and a symbol distribution θ x (which specifies a probability distribution over non-terminal and pre-terminal symbols).
A number of small variations of this traditional ITG model havebeen proposed in the literature, but we use the following generative story as a representative of previously proposed models.

Fig. 2 An example of part of the phrase table with source phrases e, target
phrases f , and feature functions φi .

Fig. 3 A straight (a) and inverted (b) ITG production.

Electronic Preprint for Journal of Information Processing Vol.20 No.2

( 1 ) Generate symbol x from the multinomial distribution
P x (x; θ x ). x can take the values term, str, or inv.
( 2 ) According to the value of x take the following actions.
( a ) If x = term, the pre-terminal, generate a phrase pairfrom the phrase table Pt (e, f ; θt ).
( b ) If x = str, a straight ITG non-terminal, generate phrase
pairs e1 , f 1  and e2 , f 2  from P f lat , and concatenate
them into a single phrase pair e1 e2 , f 1 f 2 .
( c ) If x = inv, an inverted ITG non-terminal, follows thesame process as (b), but concatenate f 1 and f 2 in reverse order e1 e2 , f 2 f 1 .
The result of this generative process is a bilingual phrase pair,along with its corresponding generative probability. We will referto this model as flat.
ITG-based models can be used to find alignments for words inparallel sentences through the process of biparsing [34]. Within
the previously described ITG framework, a sentence pair E, F
can be defined as the phrase pair that is generated by the nodeat the top of the derivation tree. Biparsing for ITGs finds themost likely derivation for this sentence pair given the ITG probabilities. Once we have this most likely derivation, we treat allphrase pairs that were generated from the same terminal symbols
as aligned (for example, in Fig. 3 : “i/il me,” “hate/coûte,” “to/de,”“admit/admettre,” and “it/le”).

4. Bayesian Modeling for Inversion Transduction Grammars
The probabilities of ITG models can be calculated in the samemanner as traditional unsupervised PCFGs using the expectationmaximization algorithm and maximum likelihood estimation.
However, as noted by Ref. [12], when many-to-many alignments
are allowed, the solution that maximizes the likelihood is often to
simply memorize every sentence as a single phrase pair, a degenerate solution that defeats the purpose of performing alignment.
Reference [35] and others propose dealing with this problem byputting a prior probability P(θ x , θt ) on the parameters, which allows us to bias towards compact models and prevent this degenerate solution.
Priors based on Bayesian statistics have proven useful for controlling model complexity in previous work, so we adapt a similar
approach here. The symbol distribution parameters θ x specify amultinomial distribution over 3 elements. Because of this it is natural to use a Dirichlet distribution as a prior for θ x , as the Dirichlet
distribution is the conjugate prior of the multinomial distribution.
θ x ∼ Dirichlet(α).

(3)α is a hyper-parameter controlling the sparsity of the distribution,
but this has little empirical eﬀect on the results, so we arbitrarily
set α = 1.
The phrase table parameters θt specify a multinomial distribution over an undetermined number of elements (every possible
phrase pair). Previous work on both word alignment [2], [35] andother natural language processing tasks has used Bayesian nonparametric techniques to specify priors over these sort of infinite
multinomial distributions. In particular we use a prior based on
the non-parametric Pitman-Yor process [31], [33]. The Pitman-c 2012 Information Processing Society of Japan

Yor process is a generalization of the better-known Dirichlet process prior that has been used in previous work on word alignment.
This prior is expressed asθt ∼PY(d, s, Pbase ).

(4)

In the Pitman-Yor process, d is the discount parameter, s is thestrength parameter, and Pbase is the base measure. The discountd is subtracted from observed counts, and when it is given a large
value (close to one), less frequent phrase pairs will be given lower
relative probability than more common phrase pairs. The strengths controls the overall sparseness of the distribution, and when it
is given a small value the distribution will be sparse. Pbase is theprior probability of generating a particular phrase pair, which we
describe in more detail in the following section.
Non-parametric priors are well suited for modeling the phrase
distribution because every time a phrase is generated by themodel, it is “memorized” and given higher probability. Within
the framework of the ITG model, this indicates that phrase pairsthat are generated by Pt many times are more likely to be reused (the rich-get-richer eﬀect), which results in the induction ofphrase tables with fewer, but more helpful phrases. In the flatmodel, non-terminal nodes are first generated from P x , reducing
the sentence to managable chunks, followed by the generation of
the pre-terminal from P x , then a generation of a minimal phrase
pair from Pt . As Pt will only generate a phrase pair at the endof the generative process, only phrase pairs of the smallest levelof granularity will be memorized and given higher probability by
the model.
While the Dirichlet process is simply the Pitman-Yor processwith d = 0, it has been shown that the discount parameter allows
for more eﬀective modeling of the long-tailed distributions thatare often found in natural language [33]. We confirmed in preliminary experiments (using the data described in Section 8) that
the Pitman-Yor process with automatically adjusted parameters
results in superior alignment results, outperforming the sparse
Dirichlet process priors used in previous research *1 .
4.1 Base MeasurePbase in Eq. (4) is the base measure, the prior probability ofphrase pairs according to the model. By choosing this probability appropriately, we can incorporate prior knowledge of whatphrases tend to be aligned to each other. In particular, there arethree pieces of prior knowledge that we would like to provide
through the base measure. First, we would like to minimize thenumber of phrases that are not aligned to any phrase in the otherlanguage, as we can assume that most of the phrases will havesome 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, when aligning multi-word phrases, it makes
sense to align phrases that are composed of words that are good*1

Following Ref. [33], we put priors on s (Gamma(α = 2, β = 1)) andd (Beta(α = 2, β = 2)) for the Pitman-Yor process, and sample theirvalues. These priors do not provide a strong bias towards any particular value of s or d, allowing the model freedom to choose values thatmaximize the likelihood of the training data. We set α = 1−10 for the
Dirichlet process.

Electronic Preprint for Journal of Information Processing Vol.20 No.2

translations of each-other.
Here, we adopt a formulation similar to that of Ref. [11] thatis able to satisfy all of these desiderata. Pbase is first calculated
by choosing whether to generate an unaligned phrase pair (where|e| = 0 or | f | = 0) according to a fixed probability pu . pu should
generally be a small value to minimize the number of unaligned
phrases *2 . Based on this choice, we next generate an aligned
phrase pair from Pba , or an unaligned phrase pair from Pbu .
For Pba , we use the following probability:
Pba (e, f ) =M0 (e, f )P pois (|e|; λ)P pois (| f |; λ)1M0 (e, f ) =(Pm1 ( f |e)Puni (e)Pm1 (e| f )Puni ( f )) 2 .
P pois is the Poisson distribution with the average length parameter λ, where k represents the phrase length | f | or |e|.
P pois (k|λ) =(λ − 1)k−1 −(λ−1)
e.
(k − 1)!

(5)

We set λ to a relatively small value, which allows us to bias
against overly long phrases *3 .
Puni is the unigram probability of a particular phrase, and Pm1
is the word-based Model 1 [3] probability of one phrase given theother. Model 1 probabilities are word-based translation probabilities that help to indicate whether the words in each phrase aregood translations of each-other. The phrase-based Model 1 probability is calculated according to the following equation:
Pm1 (e| f ) =

| f|
|e|

1 
i=1

| f | j=1

Pm1 (ei | f j )(6)where ei and f j are the ith and jth words in phrases e and f respectively. The word-based probabilities Pm1 (ei | f j ) and Pm1 ( f j |ei ) areparameters of the model, and can be calculated eﬃciently using
the expectation maximization algorithm [3] before starting phrasealignment. Following Ref. [21], we combine the Model 1 probabilities in both directions using the geometric mean *4 , which allows us to encourage alignments that are supported by both models.
For Pbu , in the case of | f | = 0, we calculate the probability as
follows:
Pbu (e, f ) = Puni (e)P pois (|e|; λ)/2.
The probability can be calculated similarly when |e| = 0. Notethat Pbu is divided by 2 as the probability is considering nullalignments in both directions.

5. Hierarchical ITG Model
While in flat only minimal phrases were memorized by themodel, as Ref. [11] notes and we confirm in the experiments in
*2
*3
*4

−2

−3

−10

We choose 10 , 10 , or 10
based on which value gave the besttranslation accuracy on the development set.
We tune λ to 1, 0.1, or 0.01 based on which value gives the best translation accuracy on the development set.
The probabilities of the geometric mean do not add to one, and are thus
not, strictly speaking, proper probabilities. However, we found empirically that even when left unnormalized, they provided much better results than the model using the arithmetic mean, which is mathematicallycorrect.

c 2012 Information Processing Society of Japan

Section 8, using only minimal phrases leads to inferior translation results for phrase-based translation. Because of this, previous research has combined flat with heuristic phrase extraction,
which exhaustively combines all adjacent phrases permitted by
the word alignments [29]. We propose an alternative, fully statistical approach that directly models phrases at multiple granularities, which we will refer to as hier. By doing so, we are able to doaway with heuristic phrase extraction, creating a phrase table thatis able to achieve competitive accuracy in a single step through afully probabilistic process.
Similarly to flat, hier assigns a probability Phier (e, f ; θ x , θt )to phrase pairs, and is parameterized by a phrase table θt and asymbol distribution θ x . The main diﬀerence between the twomodels is that non/pre-terminal symbols and phrase pairs are generated in reverse order. While flat first generates branches of thederivation tree using P x , then generates leaves using the phrase
distribution Pt , hier first attempts to generate the full sentence
as a single phrase from Pt , then falls back to ITG-style derivations to cope with sparsity. We allow for this within the Bayesian
ITG context by defining a new base measure Pdac (“divide-andconquer”) to replace Pbase in Eq. (4), resulting in the following
distribution for θt .
θt ∼ PY(d, s, Pdac )(7)

Pdac essentially generates a single longer phrase through twogenerations and a combination of shorter phrases, allowing evenlong phrase pairs to be given significant amounts of probability
when justified. The generative process of Pdac , similar to that ofP f lat from the previous section, is as follows:( 1 ) Generate symbol x from P x (x; θ x ). x can take the values base,str, or inv.
( 2 ) According to x take the following actions.
( a ) If x = base, generate a new phrase pair directly from
Pbase of Section 4.1.
( b ) If x = str, generate e1 , f 1  and e2 , f 2  from Phier , andconcatenate them into a single phrase pair e1 e2 , f 1 f 2 .
( c ) If x = inv, follow the same process as (b), but concatenate f 1 and f 2 in reverse order e1 e2 , f 2 f 1 .
A comparison of derivation trees for flat and hier is shownin Fig. 4. As previously described, flat first generates from thesymbol distribution P x , then from the phrase distribution Pt . On
the other hand, hier generates directly from Pt , which falls backto divide-and-conquer based on P x when necessary. The minimal
and non-minimal phrase pairs that are generated by Pt are surrounded by solid and dotted lines respectively. It can be seen thatwhile Pt in flat only generates minimal phrases, Pt in hier generates (and thus memorizes) phrases at all levels of granularity.
5.1 Length-based Parameter Tuning
There are still two problems with hier, one theoretical, and one
practical. Theoretically, hier contains itself as its base measure,and stochastic process models that include themselves as basemeasures are technically deficient, as noted in Ref. [8]. Practically, while the Pitman-Yor process in hier shares the parameterss and d over all phrase pairs in the model, long phrase pairs aremuch more sparse than short phrase pairs, and thus it is desir-Electronic Preprint for Journal of Information Processing Vol.20 No.2

Fig. 5 Learned discount values by phrase pair length.

Fig. 4

A word alignment (a), and its derivation according to flat (b), andhier (c). Solid and dotted lines indicate minimal and non-minimal
pairs respectively, and phrases memorized by the model are written in quotes under their corresponding instance of Pt . The pairhate/coûte is generated from Pbase .

able to appropriately adjust the parameters of Eq. (4) according
to phrase pair length.
In order to solve these problems, we reformulate the model sothat each phrase length l = | f | + |e| has its own phrase parameters
θt,l and symbol parameters θ x,l , which are given separate priors:
θt,l ∼ PY(d, s, Pdac,l )θ x,l ∼ Dirichlet(α)
We will call this model hlen.
The generative story is largely similar to hier with a few minorchanges. When we generate a sentence, we first choose its lengthl according to a uniform distribution over all possible sentence
lengthsl ∼ Uni f orm(1, L),
where L is the size |E| + |F| of the longest sentence in the
corpus. We then generate a phrase pair from the probability
Pt,l (e, f ) for length l. The base measure for hlen is identical to that of hier, with one minor change: when we fall backto two shorter phrases, we choose the length of the left phrasefrom ll ∼ Uni f orm(1, l − 1), set the length of the right phrase tolr = l − ll , and generate the smaller phrases from Pt,ll and Pt,lr
respectively.
It can be seen that phrases at each length are generated from
diﬀerent distributions, and thus the parameters for the PitmanYor process will be diﬀerent for each distribution. Further, as ll
and lr must be smaller than l, Pt,l no longer contains itself as abase measure, and is thus not deficient.
An example of the actual discount values learned in one of theexperiments described in Section 8 is shown in Fig. 5. It can be

c 2012 Information Processing Society of Japan

Fig. 6

The ratio of P x (str) to P x (inv) by length. Higher values indicate moremonotonic alignments.

seen that, as expected, the discounts for short phrases are lower
than those of long phrases. In particular, phrase pairs of length
up to six (for example, |e| = 3, | f | = 3) are given discounts ofnearly zero while larger phrases are more heavily discounted. We
conjecture that this is related to the observation by Ref. [20] thatusing phrases where max(|e|, | f |) ≤ 3 cause significant improvements in translation accuracy, while using larger phrases resultsin diminishing returns.
In addition, the hlen model has the potential to learn diﬀerent
ITG reordering probabilities for diﬀerent lengths. An example of
the ratio between P x (str) and P x (inv) learned for phrases of length
4 to 40 in German, Spanish, French, and Japanese is shown in
Fig. 6. It can be seen that at the shortest phrase length of 4, which
generally corresponds to the reordering of two single-word translations, German has a higher ratio than all other languages. This
is intuitive, as both French and Spanish order adjective-noun pairs
in the opposite order of English, so there should be more swapsof single words than in German, which places adjective-noun
pairs in the same order as English. On the other hand, as sentence length grows longer, French and Spanish surpass German
in monotonicity, a result of German having greater divergence insyntax from English. One typical example of this is that sentencefinal verbs must be reordered over long distances to their natural position in the middle of the sentence for English. Finally,
Japanese has significantly lower monotonicity than all of the European languages at almost all phrase pair lengths, a result of thevast diﬀerences in sentence structure between Japanese and English. In contrast, hier can only learn a single value for P x (str)and P x (inv). For German, Spanish, French, and Japanese, thevalues of P x (str)/P x (inv) were 4.83, 5.81, 4.99, and 1.83 respectively, showing that the overall preference for monotonicity or
non-monotonicity can be learned, although not in the fine-grainedElectronic Preprint for Journal of Information Processing Vol.20 No.2

manner allowed by hlen.
5.2 Implementation
Previous research has used a variety of methods to learn
Bayesian phrase based alignment models, all of which have used
Gibbs sampling as their central learning algorithm [1], [2], [11].
All of these techniques are applicable to the proposed model, but
we choose to apply the sentence-based sampling proposed by
Ref. [1], which has desirable convergence properties comparedto sampling single alignments. The majority of computation in
the sampling process takes place in the parsing step where probabilities for each possibly aligned bilingual span are calculated
to allow for proper sampling of an ITG parse tree for each sentence. Exhaustive parsing of ITGs can be performed in O(n6 ), but
this is too slow in practical situations for all but the smallest ofsentences. To solve this problem, we adopt the beam search algorithm of Ref. [32] as an approximation of full exhaustive parsing,and use a probability beam, trimming spans where the probability
is at least 1010 times smaller than that of the best hypothesis in thebucket.
One important implementation detail that is diﬀerent from previous models is the management of phrase counts. As a phrase
pair ta may have been generated from two smaller component
phrases tb and tc , when a sample containing ta is removed fromthe distribution, it may also be necessary to decrement the countsof tb and tc as well. The Chinese Restaurant Process representation of Pt [33] lends itself to a natural and easily implementable
solution to this problem. For each table representing a phrase pairta , we maintain not only the number of customers sitting at the table, but also the identities of phrases tb and tc that were originallyused when generating the table. When the count of the table ta is
reduced to zero and the table is removed, the counts of tb and tc
are also decremented.

6. Phrase Extraction
In this section, we describe both traditional heuristic phrase
extraction, and the proposed model-based extraction method.
6.1 Heuristic Phrase Extraction
The traditional method for heuristic phrase extraction fromword alignments exhaustively enumerates all phrases up to a certain length that are consistent with the alignment [29]. Aftercounts for each phrase pair e, f  have been enumerated, thesecounts are used to calculate five features used in the phrase table:• Phrase conditional probabilities: These are calculated inboth directions estimated using maximum likelihood estimation over phrase pair counts:
Pml (e| f ) = c(e, f )/c( f )Pml ( f |e) = c(e, f )/c(e).
• Lexical weighting probabilities: As many phrases havevery low counts, simple phrase conditional probabilities aresparse and often do not provide reliable information about
the correctness of the phrase pair. To solve this problem,
Ref. [20] proposes a method of breaking each phrase down
into its respective words, and using the conditional proba-c 2012 Information Processing Society of Japan

Fig. 7 The phrase, block, and word alignments used in heuristic phrase
extraction.

bilities of the words in the phrase to calculate a more robust
estimate of the phrase translation probabilities. The lexical
weighting probabilities in both directions are used as two additional features in the model.
• Phrase penalty: The last feature is a fixed penalty or bonus
for every phrase used. If it is a penalty, the model will prefer
to use fewer but longer phrases, and if it is a bonus the model
will prefer to use many shorter phrases.
These features are combined in a weighted manner to indicate
the overall score of each phrase, with the weights being learned
using a training regimen such as minimum error rate training(MERT [26]).
As a baseline, we perform heuristic phrase extraction over thealignments acquired by the flat and hier models. As the proposed
method often aligns relatively long phrases, not words, a varietyof alignment granularities can be used to create the phrase table(Fig. 7). In model heur-p, minimal phrases generated from Pt
are treated as aligned, and we perform phrase extraction on thesealignments. We also use two other techniques to create smalleralignment chunks that prevent sparsity. We perform regular sampling of the trees, but if we reach a minimal phrase generated
from Pt , we continue traveling down the tree until we reach either
a one-to-many alignment, which we will call heur-b as it createsalignments of “blocks,” or an at-most-one alignment, which wewill call heur-w as it generates word alignments. It should be
noted that forcing alignments smaller than the model suggests isonly used for generating alignments for use in heuristic extraction, and does not aﬀect the training process.
6.2 Model-Based Phrase Extraction
For our proposed model, we also are able to perform phrase
table extraction that directly utilizes the phrase probabilities
Pt (e, f ). Similarly to the heuristic phrase tables, we use conditional probabilities Pt ( f |e) and Pt (e| f ), lexical weighting probabilities, and a phrase penalty. Here, instead of using maximum
likelihood, we calculate conditional probabilities directly from Pt
probabilities:
Pt ( f |e) = Pt (e, f )
Pt (e, f˜)
Pt (e| f ) = Pt (e, f )

{ f˜:c(e, f˜)≥1}

Pt (ẽ, f ).

{ẽ:c(ẽ, f )≥1}

To limit phrase table size, we include only phrase pairs that arealigned at least once in the sample.
We also include two more features:• Model joint probability: As the proposed method assigns
a probability Pt (e, f ) to all phrase pairs, we can use this as
an additional feature.

Electronic Preprint for Journal of Information Processing Vol.20 No.2

• Span generative probability: We also use the average generative probability of each span that generated e, f  as computed by the chart parser during training. This is similar to
the joint probability, but is more reliable for low-frequency
phrases, where the model probability tends to over-estimate
the actual probability. The generative probability will behigh for common phrase pairs that are generated directlyfrom the model, and also for phrases that, while not directly
included in the model, are composed of two high probability
child phrases and thus can be assumed to be more reliable.
It should be noted that while for flat and hier Pt can be useddirectly, as hlen learns separate models for each length, we mustcombine these probabilities into a single value. We do this bysettingL˜
Pt (e, f ) = Pt,l (e, f )c(l)
c(l)
˜
l=1

for every phrase pair, where l = |e| + | f | and c(l) is the number ofphrases of length l in the sample.
We call this model-based extraction method mod.
6.3 Sample Combination
As has been noted in previous works [12], [20], exhaustive
phrase extraction tends to outperform approaches that use syntax
or generative models to limit phrase boundaries. Reference [12]states that this is because generative models choose only a single phrase segmentation, and thus throw away many good phrase
pairs that are in conflict with this segmentation.
Luckily, in the Bayesian framework it is simple to overcome
this problem by combining phrase tables from multiple samples.
In mod, we do this by taking the average of the joint probability
and span probability features, and re-calculating the conditional
probabilities from the averaged joint probabilities.

7. Related Work
While ITGs have been growing in popularity in recent years,
they are by no means the only method for word or phrase alignment. In fact, the seminal IBM models presented in Ref. [3]and the implementation provided by the open-source software
giza++ [28] are still widely used for word alignment in a large
number of systems. The IBM models, while quite powerful, arefundamentally diﬀerent from the models previously described inthis paper in that they are not able to handle many-to-many alignments. As a result, it is necessary to find one-to-many wordalignments in both directions, which allows for the capturing ofmulti-word units on both the source and target sides. These oneto-many alignments can then be combined using heuristics intoa many-to-many alignment [20]. Finally, using this alignment,
heuristic phrase extraction enumerates all possible phrases that do
not conflict with the word alignments [29]. In the next section, we
present experimental results comparing alignments acquired using the IBM models with those acquired using ITG-based alignment methods.
In addition to the previously mentioned alignment techniques,
there has also been a significant body of work on improving
phrase extraction methods (such as Refs. [23] and [16]). Refer-c 2012 Information Processing Society of Japanence [13] presented the first work on joint phrase alignment andextraction at multiple levels. While they take a supervised approach based on discriminative methods, we present a fully unsupervised generative model.
The generative probabilistic model where longer units are built
through the binary combination of shorter units that we use in thismodel was inspired by the model proposed by Ref. [10] for monolingual word segmentation using the minimum description length(MDL) framework. Our work diﬀers in that it uses Bayesian techniques instead of MDL, works on two languages instead of one,and uses words as its basic unit instead of phrases.
Adaptor grammars, models in which non-terminals memorize
subtrees that lie below them, have been used for word segmentation or other monolingual tasks [17]. The proposed method could
be thought of as a synchronous adaptor grammar over two languages. However, adaptor grammars have generally been used to
specify only two or a few levels as in the flat model in this paper, as opposed to recursive models such as hier or many-leveled
models such as hlen. One exception is the variational inference
method for adaptor grammars presented by Ref. [8] that is applicable to recursive grammars such as hier. We plan to examine
variational inference for the proposed models in future work.

8. Experimental Evaluation
We performed experiments to evaluate the proposed method ontranslation tasks from four languages, French, German, Spanish,
and Japanese, into English.
8.1 Experimental Setup
The data for French, German, and Spanish are from the 2010
Workshop on Statistical Machine Translation [4]. We use thenews commentary corpus for training the phrase table, and thenews commentary and Europarl corpora for training the LM.
For Japanese, we use data from the NTCIR patent translation
task [14]. We use the first 100 k sentences of the parallel corpus for the phrase table, and the whole parallel corpus for the
LM. Details of both corpora can be found in Table 1. Corpora
are tokenized, lower-cased, and sentences of over 40 words oneither side are removed for phrase table training. For both tasks,
we perform weight tuning and testing on specified development
and test sets. As an evaluation measure, we use case-insensitive
BLEU score [30], a widely used evaluation metric for machinetranslation.
We compare the accuracy of our proposed method of joint
phrase alignment and extraction using the flat, hier andhlen models, with a baseline of using word alignments from
Table 1 The number of words in each corpus for phrase table (PT) and LM
training, tuning, and testing.
PT (en)PT (other)LM (en)Tune (en)Tune (other)
Test (en)Test (other)de-en1.80 M
1.85 M52.7 M49.8 k
47.2 k
65.6 k
62.7 kes-en
1.62 M
1.82 M52.7 M49.8 k52.6 k
65.6 k68.1 kfr-en
1.35 M
1.56 M52.7 M49.8 k55.4 k
65.6 k72.6 kja-en
2.38 M
2.78 M
44.7 M
68.9 k80.4 k
40.4 k
48.7 kElectronic Preprint for Journal of Information Processing Vol.20 No.2

Fig. 8
Table 2The eﬀect of corpus size on the accuracy (a) and phrase table size (b) for each method(Japanese-English).

BLEU score and phrase table size by alignment method, extraction method, and samples combined. Bold numbers are not significantly diﬀerent from the best result according to the sign test
(p < 0.05) [9]. giza++ uses heur-w for phrase extraction and all other models use mod.

Align Samp
giza++
1
flat
1
hier
1
hlen
1
hier
10
hlen
10

de-en
BLEU
Size
16.62
4.91 M
13.48
136 k
16.58
1.02 M
16.49
1.17 M
16.53
3.44 M
16.51
3.74 M

es-en
BLEU
Size
22.00
4.30 M
19.15
125 k
21.79
859 k
21.57
930 k
21.84
2.56 M
21.69
3.00 M

giza++ [28] and heuristic phrase extraction. Translation is performed using the Moses phrase-based machine translation decoder [19] using the phrase tables learned by each method under consideration. Phrase reordering probabilities are calculatedusing Moses’s standard lexicalized reordering model [18] for all
experimental settings. Maximum phrase length is limited to 7 inall models, and for the LM we use an interpolated Kneser-Ney
5-gram model.
For giza++, we use the standard training regimen up to Model4, and combine alignments with the grow-diag-final-andcombination heuristic [18]. For the proposed models, we train
for 100 iterations, and use the final sample acquired at the end of
the training process for our experiments using a single sample *5 .
In addition, we also try averaging the phrase tables from the lastten samples as described in Section 6.3.
8.2 Experimental Results
The results for these experiments can be found in Table 2.
From these results it can be seen that when using a single sample,
the combination of using hier and model probabilities achieves
results approximately equal to giza++ and heuristic phrase extraction. This is the first reported result in which an unsupervised
phrase alignment model has built a phrase table directly frommodel probabilities and achieved results that compare to heuristicphrase extraction. It can also be seen that the phrase table createdby the proposed method is approximately 5 times smaller thanthat obtained by the traditional pipeline.
In addition, hier significantly outperforms flat when using themodel probabilities. This confirms that phrase tables containing*5

For most models, while likelihood continued to increase gradually for all
100 iterations, BLEU score gains plateaued after 5–10 iterations, likely
due to the strong prior information provided by Pbase . As iterations took
1.3 hours on a single processor, good translation results were achieved
in approximately 13 hours, which could further be reduced using distributed sampling [2], [24].

c 2012 Information Processing Society of Japan


fr-en
BLEU
Size
21.35
4.01 M
17.97
117 k
21.50
751 k
21.31
860 k
21.57
2.63 M
21.53
3.09 M

ja-en
BLEU
Size
23.20
4.22 M
16.10
89.7 k
23.23
723 k
23.19
820 k
23.12
2.21 M
23.20
2.70 M

only minimal phrases are not able to achieve results that competewith phrase tables that use multiple granularities.
Somewhat surprisingly, hlen consistently slightly underperforms hier. This indicates potential gains to be provided bylength-based parameter tuning were outweighed by losses due tothe increased complexity of the model. In particular, we believe
the necessity to combine probabilities from multiple Pt,l models into a single phrase table may have resulted in a distortionof the phrase probabilities. In addition, as we examine further
in Section 8.3, the assumption that phrase lengths are generated
from a uniform distribution is likely too strong, and further gains
could possibly be achieved by more accurate modeling of phrase
lengths.
It can also be seen that combining phrase tables from multiple samples improved the BLEU score for hlen, but not for hier.
This suggests that for hier, most of the useful phrase pairs discovered by the model are included in every iteration, and theincreased recall obtained by combining multiple samples does
not consistently outweigh the increased confusion caused by thelarger phrase table.
8.2.1 Eﬀect of Corpus Size
In order to ensure that the proposed method works well at alldata sizes, we also performed an experiment varying the size ofthe training corpus. As there are not large amounts of in-domain
data for the WMT news commentary task, we performed theseexperiments only on the patent task, varying the number of training sentences from 50 k to 400 k. The accuracy results are shownin Fig. 8 (a). It can be seen that the results are largely consistentacross all data sizes over, with statistically insignificant diﬀerences between hier and giza++, and hlen lagging slightly behindhier. Figure 8 (b) shows the size of the phrase table induced byeach method over the various corpus sizes. It can be seen thatthe tables created by giza++ are significantly larger at all corpus
sizes, with the diﬀerence being particularly pronounced at larger

Electronic Preprint for Journal of Information Processing Vol.20 No.2

Table 5 Examples of phrases that exist only in giza or ITG-based models.
giza only
our réduire lesin reducing theperceptuel implique une
implies aélections est
electionsdes attentes qui
the expectations thatvanteraitmight

ITG only
sensationnalisme
sensational
tapageur
flashyévoluémovingdégénèrent
degenerate
inscrireenrollTable 6 Phrase pairs that are used more often by giza than hier. #giza and #hier are the number of times
the phrase was used by each system.
Sourcelesqu’:”c’ estopérateurde la2010 .
, ou alorsqui sont
il noustravaillait

Table 3

Target
the
that
:”
it is
opérateurthe2010 .
, or
who are
we
”

#giza
529
74
33
32
32
33
2
2
2
2
2

#hier
475
38
0
0
0
2
0
0
0
0
0

Translation results and phrase table size for various phrase
extraction techniques (French-English).
flat
modheur-w
heur-bheur-p

17.97
21.52
21.45
21.56

hier

117 k
5.65 M
4.93 M
4.88 M

21.50
21.68
21.41
21.47

751 k
5.39 M
2.61 M
1.62 M

Table 4 Overlap of phrase tables. The numbers indicate the percentage ofthe phrase table in the column that is also included in the phrase
table in the row.
giza
flat
hier
hlen

giza
1.68%
9.24%
9.59%

flat
40.46%
68.72%
69.40%

hier
47.94%
14.84%
37.89%

hlen
41.54%
12.51%
31.61%-

corpus sizes.
8.2.2 Phrase Alignment/Heuristic Extraction
We also evaluated the eﬀectiveness of model-based phrase extraction compared to heuristic phrase extraction. Using the alignments from hier, we created phrase tables using model probabilities (mod), and heuristic extraction on words (heur-w), blocks(heur-b), and minimal phrases (heur-p) as described in Section 6.
The results of these experiments are shown in Table 3. It can beseen that model-based phrase extraction using hier outperforms
or insignificantly underperforms heuristic phrase extraction over
all experimental settings, while keeping the phrase table to a fraction of the size of most heuristic extraction methods.
8.3 Acquired Phrases
In addition, we performed a quantitative and qualitative analysis of the phrase tables acquired using giza, flat, hier, and hlen
for the French-English task. Phrase extraction was performed
with heur-w for giza and mod for all other alignment methods.
First, we performed an analysis of how much overlap there
was between the extracted phrase tables, the results of which are
shown in Table 4. Interestingly, the giza phrase table only covers approximately 40–50% of the acquired phrases in each of the
ITG models, despite being much larger. To help understand thec 2012 Information Processing Society of Japanhier Phrasewith noun
with verb
separate
separate
operatorofseparate
separate
separatewith comma
depravity (correct: “was working”)

diﬀerence between giza and the ITG-based methods, we examined the phrases that occurred in only the giza phrase table, as
well as the phrases that occurred in all of the other phrase tables, but not the giza phrase table (Table 5). For words foundby all of the ITG models but not giza, the majority were rare
single-word translations that were misaligned by giza due to the“garbage-collecting” phenomenon, where rare words are aligned
to too many words, and thus not extracted properly. Among theshorter phrases that were found by none of the ITG models, but
found by giza, most were the combination of one or several content words with a preposition.
In addition, we show examples of the phrases that are not justincluded in the phrase table, but actually used in translation by
giza and hier, focusing on phrase pairs that were used much more
often by one system than the other, as well as less frequent phrase
pairs that were used by one system twice, but the other system notimes. Phrase pairs more commonly used in the giza and hier systems are shown in Table 6 and Table 7 respectively. It can be seenthat as an overall trend, the giza system tends to translate function
words and punctuation in phrases together with the neighboringwords, while the hier system tends to translate these words separately, reflecting previous observations about the composition of
the respective phrase tables. This combination of function words
and punctuation into longer phrases does not change translation
results, but increases the size of the phrase table, lending a convincing explanation for why hier is able to achieve translation
results that match giza with a smaller phrase table.
The next most common case were examples where one of thetwo systems dropped a frequent word in a multi-word translation(such as “de la” above). This was a problem for both systems,
and there was not a clear trend favoring either system in thesecases. In addition, both giza and hier see words that are unknown
for one of the two systems (“opérateur” and “communiqué” respectively) due to missed alignments preventing the creation ofphrases for rarer words. Overall, giza was able to successfully
generate phrases for fewer words, resulting in a total of 4,738
untranslatable words in the test set compared to 3,843 for hier.

Electronic Preprint for Journal of Information Processing Vol.20 No.2

Table 7
Source,de.
laledéfinitif
communiquéfréquenteconnaissantmoment où

Fig. 9Phrase pairs that are used more often by hier than giza.

Target
,
of
.
the
the
final
communiquéfrequent
surplusmoment when

#giza
2,061
685
1,443
495
574
0
0
0
0
0

#hier
2,833
1,366
2,002
820
795
2
2
2
2
2

giza Phrasewith wordwith noun
with wordwith noun
with noun
done, means
declaration, communicatedfrequently
moreover (correct: “knowing”)
with “the”

The distribution of unique phrases by length (a) included in the phrase table and (b) used intranslation.

Finally, there were a number of examples where equally validtranslations with diﬀerent lexical choice (“définitif”) and syntactic form (“fréquente”), as well as examples where neither system
was able to create a translation correctly (“travaillait” and “connaissant”).
Finally, Fig. 9 shows a break-down by length of the phrases in
the acquired phrase table, as well as of the phrases that were actually used during translation. ¿From this graph it can be seen thatgiza creates large numbers of long phrases of length 6 or higher,
despite the fact that the majority of used phrases are of length 2
or 4 (for 1-to-1 or 2-to-2 translations respectively). In general the
distribution of phrases used by hier in translation is similar to thatof giza (with a slight tendency towards using shorter phrases), but
the overall distribution of extracted phrases decreases graduallywith length. flat, as expected, tends to both extract and use very
short phrases.
Comparing hier and hlen, it can be seen that their patterns arelargely similar, with the exception of phrases of length 3. Phrasesof length 3 must be 1-to-2 or 2-to-1, and thus should be less common for language pairs such as English and French where one
word tends to correspond to one word. hlen creates more 3-wordpatterns than hier because each length of phrase is given its own
unique phrase distribution. Specifically, if Pt,3 has fewer phrases
than Pt,2 and Pt,4 , it also has more probability to “give away” to
new 3-word phrases, creating an implicit bias towards creating
more new phrases of less common phrase lengths. It is possiblethat this bias can be corrected by introducing priors that preferphrase pairs where the number of words is roughly equal on bothsides. However, this will require significant expansions to the current generative story, which does not explicitly keep track of thenumber of words on each side, so we leave this to future work.

c 2012 Information Processing Society of Japan

9. Conclusion
In this paper, we presented a novel approach to joint phrasealignment and extraction through a hierarchical model using nonparametric Bayesian methods and inversion transduction grammars. Machine translation systems using phrase tables learned
directly by the proposed model were able to achieve accuracy
competitive with the traditional pipeline of word alignment andheuristic phrase extraction, the first such result for an unsupervised model.
One of the advantages of the proposed model is that it lends
itself to relatively simple extension, allowing for further gains inaccuracy through the introduction of more sophisticated alignment models. One promising future direction is the introduction of more intelligent prior knowledge through the base measure Pbase . For example, Pbase could be adjusted to take into account spelling similarities, parts of speech, phrase-based translation dictionaries, or bilingually acquired classes such as those
proposed by Ref. [25]. We also plan to refine hlen to use a more
appropriate model of phrase length than the uniform distribution,
particularly by attempting to bias against phrase pairs where oneof the two phrases is much longer than the other.
In addition, we will test probabilities learned using the proposed model with an ITG-based decoder. We will also examine
the applicability of the proposed model in the context of hierarchical phrases [6], or in alignment using syntactic structure [15].
It is also worth examining the plausibility of variational inference
as proposed by Ref. [8] in the alignment context.

Electronic Preprint for Journal of Information Processing Vol.20 No.2

Reference
[1]

[2]
[3]
[4]

[5]
[6]
[7]
[8]

[9]
[10]
[11]

[12]
[13]
[14]

[15]

[16]

[17]

[18]

[19]
[20]
[21]

[22]
[23]
[24]

Blunsom, P. and Cohn, T.: Inducing synchronous grammars with slice
sampling, Proc. Human Language Technology: The 11th Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp.238–241 (2010).
Blunsom, P., Cohn, T., Dyer, C. and Osborne, M.: A Gibbs sampler forphrasal synchronous grammar induction, Proc. 47th Annual Meetingof the Association for Computational Linguistics, pp.782–790 (2009).
Brown, P.F., Pietra, V.J., Pietra, S.A.D. and Mercer, R.L.: The Mathematics of Statistical Machine Translation: Parameter Estimation,
Computational Linguistics, Vol.19, pp.263–311 (1993).
Callison-Burch, C., Koehn, P., Monz, C., Peterson, K., Przybocki, M.
and Zaidan, O.F.: Findings of the 2010 joint workshop on statisticalmachine translation and metrics for machine translation, Proc. Joint
5th Workshop on Statistical Machine Translation and MetricsMATR,
pp.17–53 (2010).
Cherry, C. and Lin, D.: Inversion Transduction Grammar for Joint
Phrasal Translation Modeling, Proc. NAACL Workshop on Syntax andStructure in Machine Translation, pp.17–24 (2007).
Chiang, D.: Hierarchical phrase-based translation, Computational
Linguistics, Vol.33, No.2, pp.201–228 (2007).
Chomsky, N.: Three models for the description of language, IRE
Trans. Inf. Theory, Vol.2, No.3, pp.113–124 (1956).
Cohen, S.B., Blei, D.M. and Smith, N.A.: Variational inference foradaptor grammars, Proc. Human Language Technology: The 11th Annual Conference of the North American Chapter of the Association for
Computational Linguistics, pp.564–572 (2010).
Collins, M., Koehn, P. and Kučerová, I.: Clause restructuring for statistical machine translation, Proc. 43rd Annual Meeting of the Association for Computational Linguistics, pp.531–540 (2005).
de Marcken, C.: Unsupervised Language Acquisition, PhD Thesis,
Massachusetts Institute of Technology (1996).
DeNero, J., Bouchard-Côté, A. and Klein, D.: Sampling alignment
structure under a Bayesian translation model, Proc. Conference on
Empirical Methods in Natural Language Processing, pp.314–323(2008).
DeNero, J., Gillick, D., Zhang, J. and Klein, D.: Why generative
phrase models underperform surface heuristics, Proc. 1st Workshop
on Statistical Machine Translation, pp.31–38 (2006).
DeNero, J. and Klein, D.: Discriminative modeling of extraction sets
for machine translation, Proc. 48th Annual Meeting of the Association
for Computational Linguistics, pp.1453–1463 (2010).
Fujii, A., Utiyama, M., Yamamoto, M. and Utsuro, T.: Overview ofthe patent translation task at the NTCIR-7 workshop, Proc. 7th NTCIR
Workshop Meeting on Evaluation of Information Access Technologies,
pp.389–400 (2008).
Galley, M., Graehl, J., Knight, K., Marcu, D., DeNeefe, S., Wang, W.
and Thayer, I.: Scalable inference and training of context-rich syntactic translation models, Proc. 44th Annual Meeting of the Association
for Computational Linguistics, pp.961–968 (2006).
Johnson, J.H., Martin, J., Foster, G. and Kuhn, R.: Improving translation quality by discarding most of the phrasetable, Proc. Conferenceon Empirical Methods in Natural Language Processing, pp.967–975(2007).
Johnson, M., Griﬃths, T.L. and Goldwater, S.: Adaptor grammars:
A framework for specifying compositional nonparametric Bayesianmodels, Advances in Neural Information Processing Systems, Vol.19,
pp.641–648 (2007).
Koehn, P., Axelrod, A., Mayne, A.B., Callison-Burch, C., Osborne,
M. and Talbot, D.: Edinburgh system description for the 2005 IWSLT
speech translation evaluation, Proc. International Workshop on Spoken Language Translation (2005).
Koehn, P. et al.: Moses: Open Source Toolkit for Statistical MachineTranslation, Proc. 45th Annual Meeting of the Association for Computational Linguistics, pp.177–180 (2007).
Koehn, P., Och, F.J. and Marcu, D.: Statistical phrase-based translation, Proc. Human Language Technology Conference (HLT-NAACL),
pp.48–54 (2003).
Liang, P., Taskar, B. and Klein, D.: Alignment by agreement, Proc.
Human Language Technology Conference – North American Chapter of the Association for Computational Linguistics Annual Meeting(HLT-NAACL), pp.104–111 (2006).
Marcu, D. and Wong, W.: A phrase-based, joint probability model forstatistical machine translation, Proc. Conference on Empirical Methods in Natural Language Processing, pp.133–139 (2002).
Moore, R.C. and Quirk, C.: An iteratively-trained segmentation-freephrase translation model for statistical machine translation, Proc. 2nd
Workshop on Statistical Machine Translation, pp.112–119 (2007).
Newman, D., Asuncion, A., Smyth, P. and Welling, M.: Distributed
algorithms for topic models, Journal of Machine Learning Research,c 2012 Information Processing Society of Japan


[25]
[26]
[27]
[28]
[29]
[30]
[31]
[32]

[33]
[34]
[35]

Vol.10, pp.1801–1828 (2009).
Och, F.J.: An eﬃcient method for determining bilingual word classes,
Proc. 9th European Chapter of the Association for Computational Linguistics, pp.71–76 (1999).
Och, F.J.: Minimum Error Rate Training in Statistical Machine Translation, Proc. 41st Annual Meeting of the Association for Computational Linguistics, pp.160–167 (2003).
Och, F.J. and Ney, H.: Discriminative training and maximum entropy
models for statistical machine translation, Proc. 40th Annual Meetingof the Association for Computational Linguistics, pp.295–302 (2002).
Och, F.J. and Ney, H.: A Systematic Comparison of Various Statistical
Alignment Models, Computational Linguistics, Vol.29, No.1, pp.19–
51 (2003).
Och, F.J., Tillmann, C. and Ney, H.: Improved alignment models
for statistical machine translation, Proc. 4th Conference on Empirical
Methods in Natural Language Processing, pp.20–28 (1999).
Papineni, K., Roukos, S., Ward, T. and Zhu, W.-J.: BLEU: a method
for automatic evaluation of machine translation, Proc. 19th International Conference on Computational Linguistics, pp.311–318 (2002).
Pitman, J. and Yor, M.: The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator, The Annals of Probability,
Vol. 25, No. 2, pp. 855–900 (1997).
Saers, M., Nivre, J. and Wu, D.: Learning Stochastic Bracketing Inversion Transduction Grammars with a Cubic Time Biparsing Algorithm,
Proc. 11th International Workshop on Parsing Technologies, pp.29–32(2009).
Teh, Y.W.: A hierarchical Bayesian language model based on PitmanYor processes, Proc. 44th Annual Meeting of the Association for Computational Linguistics, pp.985–992 (2006).
Wu, D.: Stochastic inversion transduction grammars and bilingualparsing of parallel corpora, Computational Linguistics, Vol.23, No.3,
pp.377–403 (1997).
Zhang, H., Quirk, C., Moore, R.C. and Gildea, D.: Bayesian learning of non-compositional phrases with synchronous parsing, Proc.
46th Annual Meeting of the Association for Computational Linguistics, pp.97–105 (2008).

Graham Neubig received
his
B.S.
from University of Illinois, UrbanaChampaign, U.S.A, in 2005, and his M.E.
in informatics from Kyoto University,
Kyoto, Japan in 2010, where he is currently pursuing his Ph.D. He is a recipientof the JSPS Research Fellowship for
Young Scientists (DC1). His researchinterests include speech and natural language processing, with afocus on unsupervised learning for applications such as automatic
speech recognition and machine translation.

Taro Watanabe received his B.E. and
M.E. degrees in information science from
Kyoto University, Kyoto, Japan in 1994
and 1997, respectively, and obtained M.S.
degree in language and information technologies from the School of Computer
Science, Carnegie Mellon University in
2000. In 2004, he received his Ph.D. in
informatics from Kyoto University, Kyoto, Japan. After serving as a researcher at ATR and NTT, Dr. Watanabe is a seniorresearcher at National Institute of Information and Communications Technology. His research interests include natural language
processing, machine learning and statistical machine translation.

Electronic Preprint for Journal of Information Processing Vol.20 No.2

Eiichiro Sumita received his M.S. degree in computer science from the University of Electro-Communications in 1982
and Ph.D. degree in engineering from
Kyoto University in 1999. Dr. Sumita
is the director of multilingual translation laboratory of NICT and a visiting
professor of Kobe University Graduate
School. His research interests include machine translation ande-Learning.

Shinsuke Mori received his B.S., M.S.,
and Ph.D. degrees in electrical engineering from Kyoto University, Kyoto, Japan
in 1993, 1995, and 1998, respectively. After joining Tokyo Research Laboratory ofInternational Business Machines (IBM) in
1998, he studied the language model andits application to speech recognition andlanguage processing. He is currently an associate professor of
Academic Center for Computing and Media Studies, Kyoto University.

Tatsuya Kawahara received his B.E. in
1987, M.E. in 1989, and Ph.D. in 1995, allin information science, from Kyoto University, Kyoto, Japan. In 1990, he became a research associate in the Department of Information Science, Kyoto University. From 1995 to 1996, he was avisiting researcher at Bell Laboratories,
Murray Hill, NJ, USA. Currently, he is a professor in the Academic Center for Computing and Media Studies and an aﬃliatedprofessor in the School of Informatics, Kyoto University. He has
also been an invited researcher at ATR and NICT. He has published more than 200 technical papers on speech recognition, spoken language processing, and spoken dialogue systems. He has
been managing several speech-related projects in Japan including
a free large vocabulary continuous speech recognition software
project (http://julius.sourceforge.jp/). Dr. Kawahara received the1997 Awaya Memorial Award from the Acoustical Society ofJapan and the 2000 Sakai Memorial Award from the Information Processing Society of Japan. From 2003 to 2006, he was amember of IEEE SPS Speech Technical Committee. From 2011,
he is a secretary of IEEE SPS Japan Chapter. He was a generalchair of IEEE Automatic Speech Recognition & Understanding
workshop (ASRU 2007). He also served as a tutorial chair of
INTERSPEECH 2010. He is a senior member of IEEE.

c 2012 Information Processing Society of Japan