Hierarchical Pitman-Yor Language Model for Machine Translation
Tsuyoshi Okita
CNGL / School of Computing
Dublin City University
Dublin, Ireland
tokita@computing.dcu.ie

Abstract—The hierarchical Pitman-Yor process-basedsmoothing method applied to language model was proposedby Goldwater and by Teh; the performance of this smoothing
method is shown comparable with the modified Kneser-Ney
method in terms of perplexity. Although this method waspresented four years ago, there has been no paper which
reports that this language model indeed improves translation
quality in the context of Machine Translation (MT). Thisis important for the MT community since an improvementin perplexity does not always lead to an improvement in
BLEU score; for example, the success of word alignment
measured by Alignment Error Rate (AER) does not often
lead to an improvement in BLEU. This paper reports inthe context of MT that an improvement in perplexity reallyleads to an improvement in BLEU score. It turned out thatan application of the Hierarchical Pitman-Yor Language
Model (HPYLM) requires a minor change in the conventional
decoding process. Additionally to this, we propose a new
Pitman-Yor process-based statistical smoothing method similar
to the Good-Turing method although the performance of thisis inferior to HPYLM. We conducted experiments; HPYLM
improved by 1.03 BLEU points absolute and 6% relative for
50k EN–JP, which was statistically significant.
Keywords-Statistical Machine Translation, Statisticalsmoothing method, Hierarchical Pitman-Yor process.

Andy WayCNGL / School of Computing
Dublin City University
Dublin, Ireland
away@computing.dcu.ie

rely on either interpolation or back-off schemes.
This paper discusses a statistical smoothing method basedon (hierarchical) Pitman-Yor processes, which is a nonparametric generalization of the Dirichlet distribution that
produces power-law distributions [16], [4]. Various pieces
of research have been carried out in which hierarchicalPitman-Yor processes have been applied to language models(Hierarchical Pitman-Yor Language Model (HPYLM) [16],[11], [5]) whose generative model uses hierarchies of ngrams. This model is shown to be superior to the interpolated
Kneser-Ney methods [9] and comparable to the modified
Kneser Ney methods in terms of perplexity. HierarchicalPitman-Yor processes have been successfully applied toword segmentation as well [4], [10].
This paper is organized as follows. Section 2 reviews hierarchical Pitman-Yor process and related issues. In Section
3 our algorithm is presented; 1) how to obtain HPYLM and2) a minor change in the decoding algorithm. Experimental
results are presented in Section 4. Section 5 concludes andprovides avenues for further research.
II. P ITMAN -YOR P ROCESS AND S MOOTHING M ETHODS

I. I NTRODUCTION
Statistical approaches or non-parametric Machine Learning methods estimate some targeted statistical quantities
based on the (true) posterior distributions in a Bayesianmanner [1] or based on the underlying fixed but unknown(joint) distributions from which we assume that we sample
our training examples in a frequentist manner [17]. In
NLP (Natural Language Processing), such distributions areobserved by simply counting (joint/conditional) events, suchas c(w), c(w1 , w2 ) and c(w3 |w1 , w2 ) where w denoteswords and c(·) denotes a function to count events; sincesuch quantities are often discrete, it is unlikely that such
events will be counted incorrectly at first sight. However,
it is a well-known fact in NLP that such counting methods
are often unreliable if the size of the corpus is too small
compared to the model complexity. Researchers in NLP
often try to rectify such counting of (joint or conditional)
events using a technique known as smoothing [3], [9]. Most
smoothing techniques do not have a statistical model but

Pitman-Yor Process: The Pitman-Yor process [13]P Y (d, θ, G0 ) is a three-parametric distribution over a (base)distribution where d is a discount parameter, θ a strengthparameter, and G0 a base distribution. When d = 0,
the Pitman-Yor process reduces to a Dirichlet distribution
Dir(θG0 ). This generative procedure produces a power-law
distribution, indicating that many unique words are observed,
most of them rarely, for the following reasons: the more
words have been assigned to a draw from G0 , the more
likely subsequent words will be assigned to the draw, while
the more we draw from G0 , the more likely a new word
will be assigned to a new draw from G0 .
Chinese Restaurant Process: Let (x1 , . . . , xn ) bea training set. When the vocabulary is finite, although
P Y (d, θ, G0 ) has no known analytic form, we can describe
the Pitman-Yor process in terms of a generative procedurethat produces x1 ,x2 ,. . . iteratively by marginalized out G.
This procedure for generating words drawn from G is calleda Chinese restaurant process.

Let ck P
be the number of words assigned the value of draw
zk , c· = tk−1 ck be the current number of draws from G,
and t be the current number of draws from G0 . A Chinese
restaurant contains an infinite number of tables, each with
infinite seating capacity. Customers enter the restaurant andseat themselves. The first customer sits at the first available
table, while each of the subsequent customers sits at an
occupied table with probability proportional to the numberof customers already sitting there ck − d, or at a new
unoccupied table with probability proportional to θ + dt.
If zi is the index of the table chosen by the ith customer,
the ith customer sits at table k given the seating arrangementof the previous i − 1 customers zi = {z1 , . . . , zi−1 }) withprobability, as is shown in (1):
 ck −d1 ≤ k ≤ t.
θ+c·(1)
P (zi = k|zi ) =θ+dtk= t + 1.
θ+c·III. O UR A LGORITHM
Our algorithm addresses two concerns. The first concern
is to update our language model based on the hierarchical Pitman-Yor process-based smoothing method, which is
described in the first subsection. The second concern is toincorporate the zero probabilities based on the hierarchicalPitman-Yor process-based smoothing method. A PhraseBased Statistical Machine Translation (PB-SMT) decoder
uses constant zero probabilities for unseen phrases, while thezero probabilities based on the language model based on thehierarchical Pitman-Yor process-based smoothing method
are not constant but are different based on context, e.g. (n1)-gram hierarchies.
A. Language Model Smoothing
We describe the following generative model which uses
the Pitman-Yor process as a prior which we use in two
language models in common. For a given a context u, let
Gu (w) be the probability of the current word taking value w.
Using a Pitman-Yor process as the prior for Gu [Gu (w)]w∈W
as in (2):Gu ∼ P Y (d|u| , θ|u| , Gπ(u) )(2)where π(u) is a function whose parameter is a context u,
the discount and strength parameters are functions of thelength |u| of the context, while the mean vector is Gπ(u) ,the vector of probabilities of the current word given all but
the earliest word in the context.
Hierarchical Pitman-Yor Language Model: In the generative model which uses the Pitman-Yor process as a priorin Equation (2), let us consider π(u) as the suffix of u
consisting of all but the earliest word in Equation (2) [16].
This signifies that u is n-gram words and π(u) is (n-1)gram words; this induction of Equation (2) makes an n-gramhierarchy. Teh proposes a method to use the hierarchicalPitman-Yor processes recursively to place a prior over Gπ(u)using Equation (2), but now with parameters dπ(u) , θπ(u) andmean vector Gπ(π(u)) instead.
 Gu ∼ P Y (d|u| , θ|u| , Gπ(u )
...
(3)

G∅ ∼ P Y (d0 , θ0 , G0 )This is repeated until we get to G0 , the vector of probabilities
over the current word given the empty context ∅. Finally, weplace a prior on G0 as is shown in Equation (3), where G0 is
the global mean vector, given a uniform value of G0 = 1/V
for all w ∈ W .
The simplest inference procedure is to build a Gibbs
sampler which randomly selects n-gram words, draws abinary decision as to which (n − 1)-gram words originatedfrom, and updates the language model according to the
new lower-order n-grams [4]. A blocked Gibbs sampler
is proposed by Mochihashi et al. [10], which is originallyproposed for segmentation. This algorithm is an iterative
procedure, which randomly selects a n-gram word, removes
the “sentence” data of this n-gram word, and updates byadding a new “sentence” according to the new n-grams. This
procedure is expected to mix rapidly compared to the simple
Gibbs sampler.
By Equation (1), the predictive distribution of n-gramprobability in HPYLM is recursively calculated as in Equation (4):p(w|h) =θ + d · th·c(w|h) − d · thw+
p(w|h′ )θ + c(h)θ + c(h)(4)

where p(w|h′ ) is the same probability using a (n-1)-gramcontext h′ . The case when thw = 1 corresponds to aninterpolated Kneser-Ney smoothing [9].1
Good-Turing Pitman-Yor Language Model: In the samegenerative model which uses the Pitman-Yor process as aprior in Equation (2) once (not recursively), let us now
consider π(u) as a count-counts2 function. We refer tothis model as Good-Turing Pitman-Yor Language Model(GTPYLM). It is to be noted that count-counts nc , describedin Equation (6), is a concept appearing in Good-Turing
discounting [3]:nc+1
(6)cg = (c + 1)
nc
where cg is a modified count value used to replace c insubsequent relative frequency estimates, and nc is the number of events having count c. Our intention here is to make
1 Teh explains this in this way [16]: If we restrict t
hw· to be at most 1
as in (5),X
thw· = min(1, chw· ),chw· =
th′ w·(5)h′ :π(h′ )=hwe will obtain the same discount value so long as chw· > 0, i.e. absolute
discounting. Furthermore, supposing that the strength parameters are all
θ|h| = 0, the predictive probabilities in Equation (4) now directly reduceto the predictive probabilities given by interpolated Kneser-Ney.
2 This is also known as event-counts or count of counts.

a prior distribution Gu a power-law. Hence, this method
incorporates zero-frequencies by enforcing the distribution
to be a power-law.
By Equation (1), the predictive distribution of n-gramprobability in GTPYLM is computed as in (7):p(w|nw )=c(w|nw ) − d · tnw w+
θ + c(nw )θ + d · tnw ·p(w|nw − 1)
θ + c(nw )(7)where (nw − 1) is (nc − 1) where c = nw , p(w|nw − 1)denotes a (nw − 1) count-count distribution, and p(w|nw )denotes a nw count-count distribution.
B. Decoding Algorithm in PB-SMT
A minor difference in the decoding process is required.
In a test sentence, if we encounter unseen phrases, a conventional PB-SMT decoder looks up the probability withconstant zero-probabilities. However, our algorithm shouldlook up the corresponding probabilities based on the hierarchical Pitman-Yor processes. We calculate these zeroprobabilities using the parameters that we derived duringobtaining HPYLM.
There are two way to incorporate this: 1) just before we do
decoding, we update a language model by supplying a test
sentence in terms of zero-probabilities, and 2) we modify a
PB-SMT decoder to incorporate this difference. Due to theeasy implementation, we take the approach 1) here, but theeffect would be the same.
Our procedures are follows. Firstly, we prepare HPYLM
parameter file p0 (w) which we obtained when we calculate
HPYLM. This HPYLM parameter file contains the parameters in Chinese restaurant processes, such as the numberof tables, d, θ, and so forth. Such parameters enable us tocalculate the zero-probabilities for unseen phrases in a test
sentence. The overall algorithm to obtain updated HPYLM
is shown in Algorithm 1.
Algorithm 1 Decoder for HPYLM p(w)Given: a test sentence s̆ = {s̆1 , · · · , s̆n }, HPYLM p(w),
HPYLM parameter file p0 (w).
Step 1: By generating a possible n-gram candidate, using
p0 we update HPYLM p′ (w).
Step 2: Run a decoder which looks up updated HPYLM
p′ (w).
IV. E XPERIMENTAL R ESULTS
A. Experimental Setup
For all the experiments, we used a standard log-linear
phrase-based MT system based on Moses [8]. The GIZA++
implementation [12] of IBM Model 4 was used for wordalignment, followed by the grow-diag-final heuristics asphrase extraction. We used SRILM [14] to derive a 5-gram

language model. We performed MERT and use a Moses
decoder. The baseline 1 derived a 5-gram language model by
SRILM with modified Kneser-Ney method and the baseline
2 used with SRILM with Good-Turing method.
For the HPYLM and GTPYLM, we obtained the results
by a method using a blocked Gibbs sampler [10], which
was considerably more efficient compared to a conventional
Gibbs sampler [4], [16]. In this experiment, we used a phrase
table derived by the conventional method. Perplexity wasmeasured in terms of the same test set.
B. Experimental Results
We conducted an experimental evaluation for JP–EN on
the NTCIR-8 corpus [2] and for FR–EN and ES–EN on
Europarl [7]. We randomly extracted two training corporaof 50k and 200k sentence pairs, where we used 1,200
sentence pairs (NTCIR) and 2,000 sentence pairs (Europarl)for the development set, and 1,119 (EN-JP) / 1,251 (JP-EN)
sentence pairs (NTCIR) and 2,000 sentence pairs (Europarl;test2006) for the test set.
The results are shown in Table I. HPYLM obtained thebest results in all the cases; the best among them was 1.03
BLEU points absolute and 6% relative for 50k EN-JP which
was statistically significant verified by bootstrap resampling[6]. GTPYLM obtained the second best results in all thecases; an improvement of 0.90 BLEU points absolute and
5% relative for 50k EN-JP. These experiments also showthat the perplexity measure may be reliable for the final
performance measured by BLEU score.
V. C ONCLUSIONSThis paper presents an application of the hierarchicalPitman-Yor process-based language model to MT. Firstly,
although the performance of HPYLM was reported in termsof perplexity, there have been no reports, as far as we know,
in terms of BLEU in the MT context. We showed that there
was a gain with a minor change in the decoding process.
Although Teh reported that HPYLM showed a comparable
performance with the modified Kneser-Ney method, we
obtained better results than the modified Kneser-Ney method
here. Secondly, we proposed an alternative language modelusing the Pitman-Yor process applying the count-counts
distribution of the Good-Turing method. The performance of
this was not as successful as HPYLM, but it was better thanboth the modified Kneser-Ney and Good-Turing methods.
Furthermore, this was statistically significant.
There are several avenues for further research. Firstly, ourresults for our three language pairs under 200k sentencepairs would support the basic effectiveness of this statisticalsmoothing method for language modelling. We would liketo extend our work to different language pairs and larger
data sets. Note that for the giga-sized data, this method will
not be required since smoothing is a method to resolve thesparse data problem. Secondly, our experiments are limited

size
50k
50k
50k
50k
200k
200k
200k
200k
size
50k
50k
50k
50k
200k
200k
200k
200k
size
50k
50k
50k
50k
200k
200k
200k
200k

systembaseline1
baseline2
HPYLM
GTPYLMbaseline1
baseline2
HPYLM
GTPYLMsystembaseline1
baseline2
HPYLM
GTPYLMbaseline1
baseline2
HPYLM
GTPYLMsystembaseline1
baseline2
HPYLM
GTPYLMbaseline1
baseline2
HPYLM
GTPYLM

EN-JP
16.33
16.20
17.36
17.23
23.42
23.36
24.22
23.22
FR-EN
17.68
17.58
17.81
17.01
18.40
18.19
18.99
18.70
ES-EN
16.21
16.01
16.91
16.68
16.87
16.37
17.50
17.15

Perplexity
71.46872.43566.01267.11259.60758.58752.29553.332
Perplexity
188.269
190.874
168.221178.303
162.573165.232148.338
152.104
Perplexity
198.274
198.274
194.773
196.403168.431174.856152.312156.440

JP-EN
22.01
21.81
22.81
22.70
21.68
21.38
22.32
22.21
EN-FR
17.80
17.60
18.32
18.33
18.20
18.02
18.60
18.50
EN-ES
15.17
15.01
15.87
15.75
17.62
17.32
18.20
18.10

Perplexity
131.438
136.812116.074
120.320117.78119.13105.22110.12
Perplexity
188.329
190.314178.269
179.200
165.839168.989
153.921160.332
Perplexity
156.861
152.435
151.434
153.224154.273168.754145.223
146.211

Table IR ESULTS FOR LANGUAGE MODEL . BASELINE 1 IS BY MODIFIEDK NESER -N EY METHOD AND BASELINE 2 IS BY G OOD -T URING METHOD .

only to language models. However, it would be possible toapply a similar method to the translation model. Thirdly, we
may extend our approach to syntax-based or dependencybased LMs.
VI. ACKNOWLEDGMENTS
This research is supported by the Science Foundation
Ireland (Grant 07/CE/I1142) as part of the Centre for
Next Generation Localisation (http://www.cngl.ie)
at Dublin City University. We would also like to thank the
Irish Centre for High-End Computing.
R EFERENCES[1] C. M. Bishop, “Pattern Recognition and Machine Learning”,
Springer-Verlag London. 2006.
[2] A. Fujii, M. Utiyama, M. Yamamoto, T. Utsuro, T. Ehara,
H. Echizen-ya, S. Shimohata. “Overview of the Patent Translation Task at the NTCIR-8 Workshop”. Proceedings of the 8th
NTCIR Workshop Meeting on Evaluation of Information Access Technologies: Information Retrieval, Question Answeringand Cross-lingual Information Access. 2010. pp. 293–302.
[3] W. A. Gale. “Good-Turing Smoothing Without Tears”, Journalof Quantitative Linguistics. 1995. 2:3, pp. 217–237.
[4] S. Goldwater, T. L. Griffiths, and M. Johnson. “Contextual
dependencies in unsupervised word segmentation”. In Proceedings of Conference on Computational Linguistics / Association for Computational Linguistics (COLING-ACL06).
Sydney, Australia. July, 2006. pp. 673–680.

[5] S. Huang and S. Renals. “Hierarchical Bayesian Language
Models for Conversational Speech Recognition”. IEEE Transactions on Audio, Speech and Language Processing, 2009.
18:8, pp. 1941–1954.
[6] P. Koehn, “Statistical Significance Tests for Machine Translation Evaluation”. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP 2004),
Barcelona, Spain. 2004. pp. 388-395.
[7] P. Koehn. “Europarl: A Parallel Corpus for Statistical MachineTranslation”. In Proceedings of the 10th Machine Translation
Summit (MT Summit X), Phuket, Thailand, Sep, 2005. pp.
79–86.
[8] P. Koehn, H. Hoang, A. Birch, C. Callison-Burch, M. Federico,
N. Bertoldi, B. Cowan, W. Shen, C. Moran, R. Zens, C. Dyer,
O. Bojar, A. Constantin, and E. Herbst. “Moses: Open source
toolkit for Statistical Machine Translation”. In Proceedings ofthe 45th Annual Meeting of the Association for Computational
Linguistics Companion Volume Proceedings of the Demo andPoster Sessions, Prague, Czech Republic, 2007. pp. 177–180.
[9] R. Kneser and H. Ney. 1995. “Improved backing-off for n-gram
language modeling”. In Proceedings of the IEEE International
Conference on Acoustics, Speech and Signal Processing, vol. 1,
Detroit, MI, 1995, pp. 181–184.
[10] D. Mochihashi, T. Yamada and N. Ueda. “Bayesian Unsupervised Word Segmentation with Nested Pitman-Yor Language
Modeling”. In Proceedings of Joint Conference of the 47th
Annual Meeting of the Association for Computational Linguistics and the 4th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language
Processing (ACL-IJCNLP 2009), Singapore, August, 2009. pp.
100–108.
[11] D. Mochihashi and E. Sumita. “The Infinite Markov Model”.
In Proceedings of the 20th Neural Information Processing
Systems (NIPS 2007), Vancouver, 2007. pp. 1017–1024.
[12] F. Och and H. Ney. “A Systematic Comparison of Various Statistical Alignment Models”. Computational Linguistics, 29:1,
2003. pp. 19-51.
[13] J. Pitman. “Exchangeable and partially Exchangeable Random Partitions”. Probability Theory and Related Fields, Vol.
102, pp. 145-158, 1995.
[14] A. Stolcke. “SRILM – An extensible language modeling
toolkit”. In Proceedings of the International Conference on
Spoken Language Processing. 2002. pp. 901–904.
[15] E. Sudderth and M. Jordan. “Shared Segmentation of Natural
Scenes using Dependent Pitman-Yor Processes”. In Proceedings of the 21th Neural Information Processing Systems (NIPS
2008), Vancouver, Dec, 2008. pp. 1585–1592.
[16] Y. W. Teh. “A hierarchical Bayesian language model based on
Pitman-Yor processes”. In Proceedings of Joint Conference ofthe 44th Annual Meeting of the Association for Computational
Linguistics, Sydney, Australia, 2006. pp. 985–992.
[17] V. Vapnik. “Statistical Learning Theory”. John Wiley & Sons,
1998.