An Empirical Study of Smoothing Techniques for
Language Modeling
Citation
Chen, Stanley F. and Joshua Goodman. 1998. An Empirical Study of Smoothing Techniques for
Language Modeling. Harvard Computer Science Group Technical Report TR-10-98.

Permanent link
http://nrs.harvard.edu/urn-3:HUL.InstRepos:25104739

Terms of Use
This article was downloaded from Harvard University’s DASH repository, and is made available
under the terms and conditions applicable to Other Posted Material, as set forth at http://
nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA

Share Your Story
The Harvard community has made this article openly available.
Please share how this access benefits you. Submit a story .
Accessibility

An Empirical Study of Smoothing Techniques for
Language Modeling
Stanley F. Chen
and
Joshua Goodman
TR-10-98
August 1998

Computer Science Group
Harvard University
Cambridge, Massachusetts

An Empirical Study of Smoothing Techniques for Language
Modeling
Stanley F. Chen
School of Computer Science
Carnegie Mellon University
5000 Forbes Ave.
Pittsburgh, PA 15213
sfc@cs.cmu.edu

Joshua Goodman
Engineering Sciences Laboratory
Harvard University
40 Oxford St.
Cambridge, MA 02138
goodman@eecs.harvard.edu

July 24, 1998
Abstract

We present a tutorial introduction to n-gram models for language modeling and survey
the most widely-used smoothing algorithms for such models. We then present an extensive
empirical comparison of several of these smoothing techniques, including those described by
Jelinek and Mercer (1980), Katz (1987), Bell, Cleary, and Witten (1990), Ney, Essen, andKneser (1994), and Kneser and Ney (1995). We investigate how factors such as training data
size, training corpus (e.g., Brown versus Wall Street Journal), count cuto s, and n-gram order(bigram versus trigram) a ect the relative performance of these methods, which is measured
through the cross-entropy of test data. Our results show that previous comparisons have notbeen complete enough to fully characterize smoothing algorithm performance. We introduce
methodologies for analyzing smoothing algorithm ecacy in detail, and using these techniques
we motivate a novel variation of Kneser-Ney smoothing that consistently outperforms all otheralgorithms evaluated. Finally, results showing that improved language model smoothing leads
to improved speech recognition performance are presented.

1 Introduction
Language models are a staple in many domains including speech recognition, optical character
recognition, handwriting recognition, machine translation, and spelling correction (Church, 1988;
Brown et al., 1990; Hull, 1992; Kernighan, Church, and Gale, 1990; Srihari and Baltus, 1992).
The dominant technology in language modeling is n-gram models, which are straightforward toconstruct except for the issue of smoothing, a technique used to better estimate probabilities when
there is insucient data to estimate probabilities accurately. An enormous number of techniques
have been proposed for smoothing n-gram models, many more than we could possibly describe
here; however, there has been a conspicuous absence of studies that systematically compare therelative performance of more than just a few of these algorithms on multiple data sets. As a result,from the literature it is impossible to gauge the relative performance of existing algorithms in all
but a handful of situations.
In this work, we attempt to dispel some of the mystery surrounding smoothing by determining
which algorithms work well in which situations, and why. We begin by giving a tutorial introduction2

to n-gram models and smoothing, and survey the most widely-used smoothing techniques. We thenpresent an extensive empirical comparison of several of these smoothing techniques, including thosedescribed by Jelinek and Mercer (1980), Katz (1987), Bell, Cleary, and Witten (1990), Ney, Essen,
and Kneser (1994), and Kneser and Ney (1995). We describe experiments that systematically varya wide range of variables, including training data size, corpus, count cuto s, and n-gram order, andshow that most of these variables signi cantly a ect the relative performance of algorithms. We
introduce methodologies for analyzing smoothing algorithm performance in detail, and using thesetechniques we motivate a novel variation of Kneser-Ney smoothing that consistently outperforms allother algorithms evaluated. Finally, we present results showing that better smoothing algorithms
lead to better speech recognition performance, yielding up to a 1% absolute di erence in word-error
rate. This work is an extension of our previously reported research (Chen and Goodman, 1996;
Chen, 1996).
This paper is structured as follows: In the remainder of this section, we present an introduction
to language modeling, n-gram models, and smoothing. In Section 2, we survey previous work onsmoothing n-gram models. In Section 3, we describe our novel variation of Kneser-Ney smoothing.
In Section 4, we discuss various aspects of our experimental methodology, including the details of
our implementations of various smoothing algorithms, parameter optimization, and data sets. In
Section 5, we present the results of all of our experiments. Finally, in Section 6 we summarize themost important conclusions of this work.

1.1 Language Modeling and n-Gram Models

A language model is usually formulated as a probability distribution p(s) over strings s that
attempts to re ect how frequently a string s occurs as a sentence. For example, for a language model describing spoken language, we might have p(hello)  0:01 since perhaps oneout of every hundred sentences a person speaks is hello. On the other hand, we would havep(chicken funky overload ketchup)  0 and p(asbestos gallops gallantly)  0 since
it is extremely unlikely anyone would utter either string. Notice that unlike in linguistics, grammaticality is irrelevant in language modeling; even though the string asbestos gallops gallantly
is grammatical, we still assign it a near-zero probability.
The most widely-used language models, by far, are n-gram language models. We introduce
these models by considering the case n = 2; these models are called bigram models. First, we
notice that for a sentence s composed of the words w1    wl , without loss of generality we can
express p(s) as

p(s) = p(w1 )p(w2 jw1 )p(w3 jw1 w2 )    p(wl jw1    wl 1 ) =

l
Y
i=1

p(wi jw1    wi 1 )In bigram models, we make the approximation that the probability of a word depends only on theidentity of the immediately preceding word, giving usp(s) =lY
i=1

p(wi jw1    wi 1 ) 

l
Y
i=1

p(wi jwi 1 )(1)

To make p(wi jwi 1 ) meaningful for i = 1, we can pad the beginning of the sentence with adistinguished token <bos>; thatPis, we pretend w0 is <bos>. In addition, to make the sumof the probabilities of all strings s p(s) equal 1, it is necessary to place a distinguished token
3<eos> at the end of sentences and to include this in the product in equation (1).1 For example,
to calculate p(John read a book) we would takep(John read a book) = p(Johnj<bos>)p(readjJohn)p(ajread)p(bookja)p(<eos>jbook)To estimate p(wi jwi 1 ), the frequency with which the word wi occurs given that the last word
is wi 1 , we can simply count how often the bigram wi 1 wi occurs in some text and normalize. Letc(wi 1 wi ) denote the number of times the bigram wi 1 wi occurs in the given text. Then, we cantakep(wi jwi 1 ) = Pc(wc(i w1 wi )w )
(2)
i 1 i
wi
The text available for building a model is called training data. For n-gram models, the amountof training data used is typically many millions of words. The estimate for p(wi jwi 1 ) given inequation (2) is called the maximum likelihood (ML) estimate of p(wi jwi 1 ), because this assignmentof probabilities yields the bigram model that assigns the highest probability to the training dataof all possible bigram models.
For n-gram models where n > 2, instead of conditioning the probability of a word on theidentity of just the preceding word, we condition this probability on the identity of the last n 1
words. Generalizing equation (1) to n > 2, we getp(s) =lY+1
i=1

p(wi jwii n1 +1 )(3)

where wij denotes the words wi    wj and where we take w n+2 through w0 to be <bos> and wl+1
to be <eos>. To estimate the probabilities p(wi jwii n1 +1 ), the analogous equation to equation (2)isip(wi jwii n1 +1 ) = Pc(wc(i wni+1 ) )
(4)
wi

i n+1

In practice, the largest n in wide use is n = 3; this model is referred to as a trigram model. The
wordsPwii n1 +1 preceding the current word wi are sometimes called the history. Notice that thesum wi c(wii n+1 ) is equal to the count of the history c(wii n1 +1 ); both forms are used in thistext.
We sometimes refer to the value n of an n-gram model as its order. This terminology comesfrom the area of Markov models (Markov, 1913), of which n-gram models are an instance. In
particular, an n-gram model can be interpreted as a Markov model of order n 1.
Let us consider a small example. Let our training data S be composed of the three sentences(\John read Moby Dick"; \Mary read a different book"; \She read a book by Cher")and let us calculate p(John read a book) for the maximum likelihood bigram model. We haveJohn) 1p(Johnj<bos>) = cP(<bos>
c
(
<bos>
w) = 3wc(John read) = 1
p(readjJohn) = P
w c(John w) 1

1 Without this, the sum of the probabilities of all strings of a given length is 1, and the sum of the probabilitiesof all strings is then in nite.

4c(read a) = 2
w c(read w) 3p(ajread) =Pc(a book) = 1
p(bookja) = P
w c(a w) 2
(book <eos>) = 1
p(<eos>jbook) = cPc(book w) 2
w

giving usp(John read a book) = p(Johnj<bos>)p(readjJohn)p(ajread)p(bookja)p(<eos>jbook)= 13  1  23  21  12
 0:06

1.2 SmoothingNow, consider the sentence Cher read a book. We havec(Cher read) = 0
p(readjCher) = P
w c(Cher w) 1
giving us p(Cher read a book) = 0. Obviously, this is an underestimate for the probability ofCher read a book as there is some probability that the sentence occurs. To show why it isimportant that this probability should be given a nonzero value, we turn to the primary application
for language models, speech recognition. In speech recognition, one attempts to nd the sentence sthat maximizes p(sjA) = p(Apj(sA)p)(s) for a given acoustic signal A. If p(s) is zero, then p(sjA) will be
zero and the string s will never be considered as a transcription, regardless of how unambiguous theacoustic signal is. Thus, whenever a string s such that p(s) = 0 occurs during a speech recognitiontask, an error will be made. Assigning all strings a nonzero probability helps prevent errors inspeech recognition.
Smoothing is used to address this problem. The term smoothing describes techniques foradjusting the maximum likelihood estimate of probabilities (as in equations (2) and (4)) to produce
more accurate probabilities. The name smoothing comes from the fact that these techniques
tend to make distributions more uniform, by adjusting low probabilities such as zero probabilities
upward, and high probabilities downward. Not only do smoothing methods generally prevent zeroprobabilities, but they also attempt to improve the accuracy of the model as a whole. Whenevera probability is estimated from few counts, smoothing has the potential to signi cantly improve
estimation.
To give an example, one simple smoothing technique is to pretend each bigram occurs once
more than it actually does (Lidstone, 1920; Johnson, 1932; Je reys, 1948), yieldingc(wi 1 wi ) = 1 +Pc(wi 1 wi )(5)p(wi jwi 1 ) = P 1 +[1
wi + c(wi 1 wi )] jV j + wi c(wi 1 wi )where V is the vocabulary, the set of all words being considered.2 Let us reconsider the previous
example using this new distribution, and let us take our vocabulary V to be the set of all words
occurring in the training data S , so that we have jV j = 11.
2 Notice that if V is taken to be in nite, the denominator is in nite and all probabilities are set to zero. In
practice, vocabularies are typically xed to be tens of thousands of words or less. All words not in the vocabulary
are mapped to a single distinguished word, usually called the unknown word.

5

bigramtrigramJelinek-Mercer Nadas Katz
118
119 11789
91
88

Table 1: Perplexities reported by Katz and Nadas on 100-sentence test set for three di erent
smoothing algorithms
For the sentence John read a book, we now havep(John read a book) = p(Johnj<bos>)p(readjJohn)p(ajread)p(bookja)p(<eos>jbook)2  2  3  2  2  0:0001= 14
12 14 13 13

In other words, we estimate that the sentence John read a book occurs about once every ten
thousand sentences. This is much more reasonable than the maximum likelihood estimate of 0.06,
or about once every seventeen sentences. For the sentence Cher read a book, we havep(Cher read a book) = p(Cherj<bos>)p(readjCher)p(ajread)p(bookja)p(<eos>jbook)1  1  3  2  2  0:00003= 14
12 14 13 13

Again, this is more reasonable than the zero probability assigned by the maximum likelihood
model.
While smoothing is a central issue in language modeling, the literature lacks a de nitive comparison between the many existing techniques. Previous studies (Nadas, 1984; Katz, 1987; Church
and Gale, 1991; MacKay and Peto, 1995; Kneser and Ney, 1995) only compare a small number ofmethods (typically two) on one or two corpora and using a single training set size. As a result, it
is currently dicult for a researcher to intelligently choose among smoothing schemes.
In this work, we carry out an extensive empirical comparison of the most widely-used smoothing
techniques, including those described by Jelinek and Mercer (1980), Katz (1987), Bell, Cleary,and Witten (1990), Ney, Essen, and Kneser (1994), and Kneser and Ney (1995). We carry out
experiments over many training set sizes on varied corpora using n-grams of various order, and show
how these factors a ect the relative performance of smoothing techniques. For the methods withparameters that can be tuned to improve performance, we perform an automated search for optimalvalues and show that sub-optimal parameter selection can signi cantly decrease performance. To
our knowledge, this is the rst smoothing work that systematically investigates any of these issues.
Our results make it apparent that previous evaluations of smoothing techniques have not beenthorough enough to provide an adequate characterization of the relative performance of di erent
algorithms. For instance, Katz (1987) compares his algorithm with an unspeci ed version of
Jelinek-Mercer deleted estimation and with Nadas smoothing (Nadas, 1984) using a single training
corpus and a single test set of 100 sentences. The perplexities reported are displayed in Table 1.
Katz concludes that his algorithm performs at least as well as Jelinek-Mercer smoothing and Nadassmoothing. In Section 5.1.1, we will show that, in fact, the relative performance of Katz andJelinek-Mercer smoothing depends on training set size, with Jelinek-Mercer smoothing performing
better on smaller training sets, and Katz smoothing performing better on larger sets.
In addition to evaluating the overall performance of various smoothing techniques, we provide
more detailed analyses of performance. We examine the performance of di erent algorithms on
n-grams with particular numbers of counts in the training data; we nd that Katz smoothing6performs well on n-grams with large counts, while Kneser-Ney smoothing is best for small counts.
We calculate the relative impact on performance of small counts and large counts for di erent
training set sizes and n-gram orders, and use this data to explain the variation in performanceof di erent algorithms in di erent situations. Finally, we use this detailed analysis to motivate amodi cation to Kneser-Ney smoothing; the resulting algorithm consistently outperforms all otheralgorithms evaluated.
While smoothing is one technique for addressing sparse data issues, there are numerous othertechniques that can be applied, such as word classing (Brown et al., 1992b) or decision-tree models(Bahl et al., 1989). However, these other techniques involve the use of models other than n-grammodels. We constrain our discussion of smoothing to techniques where the structure of a modelis unchanged but where the method used to estimate the probabilities of the model is modi ed.
Smoothing can be applied to these alternative models as well, and it remains to be seen whether
improved smoothing for n-gram models will lead to improved performance for these other models.

1.3 Performance Evaluation

The most common metric for evaluating a language model is the probability that the model assigns
to test data, or the derivative measures of cross-entropy and perplexity. For a smoothed n-grammodel that has probabilities p(wi jwii n1 +1 ), we can calculate the probability of a sentence p(s) using
equation (3). Then, for a test set T composed of the sentences (t1 ; : : : ; tlT ) we can calculate theprobability of the test set p(T ) as the product of the probabilities of all sentences in the set:p(T ) =

lTY
i=1

p(ti )The measure of cross-entropy can be motivated using the well-known relation between prediction and compression (Bell, Cleary, and Witten, 1990; Cover and Thomas, 1991). In particular,
given a language model that assigns probability p(T ) to a text T , we can derive a compression
algorithm that encodes the text T using log2 p(T ) bits. The cross-entropy Hp (T ) of a modelp(wi jwii n1 +1 ) on data T is de ned as

Hp (T ) = W1 log2 p(T )(6)Twhere WT is the length of the text T measured in words.3 This value can be interpreted as
the average number of bits needed to encode each of the WT words in the test data using thecompression algorithm associated with model p(wi jwii n1 +1 ). We sometimes refer to cross-entropy

as just entropy.
The perplexity PPp (T ) of a model p is the reciprocal of the (geometric) average probability
assigned by the model to each word in the test set T , and is related to cross-entropy by the equation
PPp (T ) = 2Hp (T )Clearly, lower cross-entropies and perplexities are better. Typical perplexities yielded by n-grammodels on English text range from about 50 to almost 1000 (corresponding to cross-entropies fromabout 6 to 10 bits/word), depending on the type of text.
3 In this work, we include the end-of-sentence token <eos> when computing WT , but not the beginning-ofsentence tokens.

7

In this work, we take the performance of an algorithm to be its cross-entropy on test data. As
the cross-entropy of a model on test data gives the number of bits required to encode that data,cross-entropy is a direct measure of application performance for the task of text compression. For
other applications, it is generally assumed that lower entropy correlates with better performance.
For speech recognition, it has been shown that this correlation is reasonably strong (Chen, Beeferman, and Rosenfeld, 1998). In Section 5.3.3, we present results that indicate that this correlation
is especially strong when considering only n-gram models that di er in the smoothing techniqueused.

2 Previous WorkIn this section, we survey a number of smoothing algorithms for n-gram models. This list is by nomeans exhaustive, but includes the algorithms used in the majority of language modeling work.
The algorithms (except for those described in Section 2.9) are presented in chronological order of
introduction.
We rst describe additive smoothing, a very simple technique that performs rather poorly.
Next, we describe the Good-Turing estimate; this technique is not used alone, but is the basis forlater techniques such as Katz smoothing. We then discuss Jelinek-Mercer and Katz smoothing,
two techniques that generally work well. After that, we describe Witten-Bell smoothing; while
Witten-Bell smoothing is well-known in the compression community, we will later show that it
has mediocre performance compared to some of the other techniques we describe. We go on to
discuss absolute discounting, a simple technique with modest performance that forms the basis forthe last technique we describe, Kneser-Ney smoothing. Kneser-Ney smoothing works very well,and variations we describe in Section 3 outperform all other tested techniques. In Section 2.8, we
describe a simple framework that can be used to express most popular smoothing methods, andrecap the surveyed algorithms in terms of this framework.
This section summarizes the original descriptions of previous algorithms, but does not include
the details of our implementations of these algorithms; this information is presented instead in
Section 4.1. As many of the original texts omit important details, our implementations sometimes
di er signi cantly from the original algorithm description.

2.1 Additive Smoothing

One of the simplest types of smoothing used in practice is additive smoothing (Lidstone, 1920;
Johnson, 1932; Je reys, 1948), which is just a generalization of the method given in equation (5).
Instead of pretending each n-gram occurs once more than it does, we pretend it occurs  times
more than it does, where typically 0 <   1, i.e.,i(7)
padd(wi jwii n1 +1 ) = jV j++Pc(wic(nw+1i ) )i n+1
wi
Lidstone and Je reys advocate taking  = 1. Gale and Church (1990; 1994) have argued that thismethod generally performs poorly.

2.2 Good-Turing Estimate

The Good-Turing estimate (Good, 1953) is central to many smoothing techniques. The GoodTuring estimate states that for any n-gram that occurs r times, we should pretend that it occurs
8r times wherer = (r + 1) nnr+1(8)
pGT ( ) = rN

(9)r

and where nr is the number of n-grams that occur exactly r times in the training data. To convert
this count to a probability, we just normalize: for an n-gram with r counts, we takeP
where N = 1
r=0 nr r . Notice that

N=

1
X
r=0

nr r =

1X
r=0

(r + 1)nr+1 =

1
X
r=1

rnr

i.e., N is equal to the original number of counts in the distribution.
To derive this estimate, assume that there are a total of s di erent n-grams 1 ; : : : ; s andthat their true probabilities or frequencies are p1 ; : : : ; ps , respectively. Now, let us estimate thetrue probability of an n-gram i that occurs r times in some data, given that we don't know theidentity of the n-gram i but that we do know the candidate probabilities p1 ; : : : ; ps . We caninterpret this as calculating the value E (pi jc( i ) = r), where E denotes expected value and wherec( i ) denotes the number of times the n-gram i occurs in the given data. This can be expanded
as
s
X
(10)
E (pi jc( i ) = r) = p(i = j jc( i ) = r)pj
j =1

The probability p(i = j jc( i ) = r) is the probability that an unknown n-gram i with r counts is
actually the j th n-gram j (with corresponding frequency pj ). We can rewrite this as

N pr (1 p )N rpr (1 p )N rp(i = j jc( i ) = r) = Psp(c(p(cj() =)r=) r) = Ps r Nj r j N r = Ps j pr (1 j p )N r
jjj =1
j =1 jj =1 r pj (1 pj )Pwhere N = sj=1 c( j ), the total number of counts. Substituting this into equation (10), we getPs
prj +1(1 pj )N r
E (pi jc( i ) = r) = Pj=1
(11)
s pr (1 p )N r
jj =1 jNow, consider EN (nr ), the expected number of n-grams with exactly r counts given that there
are a total of N counts. This is equal to the sum of the probability that each n-gram has exactly
r counts:s N sX
Xr
N r
EN (nr ) = p(c( j ) = r) =r pj (1 pj )
j =1

j =1

We can substitute this expression into equation (11) to yield)
E (pi jc( i ) = r) = Nr ++11 ENE+1 ((nnr+1)
N rThis is an estimate for the expected probability of an n-gram i with r counts; to express this interms of a corrected count r we use equation (9) to get)  (r + 1) nr+1r = Np( i ) = N Nr ++11 ENE+1 ((nnr+1
nr
N r)
9

Notice that the approximations EN (nr )  nr and EN +1 (nr+1 )  nr+1 are used in the above
equation. In other words, we use the empirical values of nr to estimate what their expected values
are.
The Good-Turing estimate cannot be used when nr = 0; it is generally necessary to \smooth"the nr , e.g., to adjust the nr so that they are all above zero. Recently, Gale and Sampson (1995)
have proposed a simple and e ective algorithm for smoothing these values.
In practice, the Good-Turing estimate is not used by itself for n-gram smoothing, because it
does not include the combination of higher-order models with lower-order models necessary forgood performance, as discussed in the following sections. However, it is used as a tool in several
smoothing techniques.4

2.3 Jelinek-Mercer Smoothing

Consider the case of constructing a bigram model on training data where we have that c(burnish the) =0 and c(burnish thou) = 0. Then, according to both additive smoothing and the Good-Turing
estimate, we will havep(thejburnish) = p(thoujburnish)
However, intuitively we should havep(thejburnish) > p(thoujburnish)
because the word the is much more common than the word thou. To capture this behavior, we
can interpolate the bigram model with a unigram model. A unigram model (or 1-gram model)
conditions the probability of a word on no other words, and just re ects the frequency of words intext. For example, the maximum likelihood unigram model ispML(wi ) = Pc(wc(i )w )i
wi
We can linearly interpolate a bigram model and unigram model as follows:

pinterp(wi jwi 1 ) =  pML (wi jwi 1 ) + (1 ) pML (wi )where 0    1. Because pML(thejburnish) = pML (thoujburnish) = 0 while presumablypML (the)  pML(thou), we will have thatpinterp(thejburnish) > pinterp(thoujburnish)
as desired.
In general, it is useful to interpolate higher-order n-gram models with lower-order n-grammodels, because when there is insucient data to estimate a probability in the higher-order model,
the lower-order model can often provide useful information. A general class of interpolated models

4 One issue in applying the Good-Turing estimate is deciding which distribution to apply it to. That is, we canapply it to a joint distribution on n-grams, e.g., the joint distribution on bigrams p(wi 1 wi ). We can then convert
the corrected counts r into conditional probabilities p(wi jwi 1 ). Another choice, however, is to apply it to eachconditional distribution separately, e.g., to the distribution p(wi jwi 1 ) for each wi 1 . With the former strategy,
there is plenty of data to estimate the r accurately; however, r will only represent a good average value over all
conditional distributions. The ideal adjustment of a count changes between conditional distributions. While taking
the latter strategy can exhibit this behavior, data sparsity is a problem in estimating the r . In the smoothingalgorithms to be described, Katz smoothing uses the former strategy, while the latter perspective can be viewed as
motivating Witten-Bell smoothing and absolute discounting.

10

is described by Jelinek and Mercer (1980). An elegant way of performing this interpolation is given
by Brown et al. (1992a) as follows

pinterp(wi jwii n1 +1 ) = wii n1 +1 pML (wi jwii n1 +1 ) + (1 wii n1 +1 ) pinterp(wi jwii n1 +2 )(12)That is, the nth-order smoothed model is de ned recursively as a linear interpolation between
the nth-order maximum likelihood model and the (n 1)th-order smoothed model. To end therecursion, we can take the smoothed 1st-order model to be the maximum likelihood distribution,
or we can take the smoothed 0th-order model to be the uniform distributionp (w ) = 1
unif

i

jV j

Given xed pML , it is possible to search eciently for the wii n1 +1 that maximize the probabilityof some data using the Baum-Welch algorithm (Baum, 1972). To yield meaningful results, the data
used to estimate the wii n1 +1 need to be di erent from the data used to calculate the pML .5 In
held-out interpolation, one reserves a section of the training data for this purpose, where this heldout data is not used in calculating the pML . Alternatively, Jelinek and Mercer describe a techniqueknown as deleted interpolation or deleted estimation where di erent parts of the training datarotate in training either the pML or the wii n1 +1 ; the results are then averaged.
Notice that the optimal wii n1 +1 will be di erent for di erent histories wii n1 +1 . For example,
for a context we have seen thousands of times, a high  will be suitable since the higher-order
distribution will be very reliable; for a history that has occurred only once, a lower  will beappropriate. Training each parameter wii n1 +1 independently is not generally felicitous; we would
need an enormous amount of data to train so many independent parameters accurately. Instead,
Jelinek and Mercer suggest dividing the wii n1 +1 into a moderate number of partitions or buckets,and constraining all wii n1 +1 in the same bucket to have the same value, thereby reducing thenumber of independent parameters to be estimated. Ideally, we should tie together those wii n1 +1that we have an a priori reason to believe should have similar
P values. Bahl, Jelinek, and Mercer(1983) suggest choosing these sets of wii n1 +1 according to wi c(wii n+1 ), the total number ofcounts in the higher-order distribution being interpolated (which is equal to the number of countsof the corresponding history). As touched on above, this total count should correlate with howstrongly the higher-order distribution should be weighted; the higher this count, the higher wii n1 +1
should be. More speci cally, Bahl et al. suggest partitioning the range of possible total countvalues and taking all wii n1 +1 associated with the same partition to be in the same bucket. In
previous work (Chen, 1996), we show that
according to the average number of counts
P bucketing
i n+1 )c(w
i
per nonzero element in a distribution jwi :wc(iwii n+1)>0j yields better performance than using thePvalue wi c(wii n+1 ).

2.4 Katz Smoothing

Katz smoothing (1987) extends the intuitions of the Good-Turing estimate by adding the combination of higher-order models with lower-order models. We rst describe Katz smoothing for
5 When the same data is used to estimate both, setting all  i 1

wi n+1 to one yields the optimal result.

11

bigram models. For a bigram wii 1 with count r = c(wii 1 ), we calculate its corrected count using
the equation0ckatz(wii 1 ) = dr(rw ) p (w ) ifif rr >
(13)
=0
i 1

ML

i

That is, all bigrams with a nonzero count r are discounted according to a discount ratio dr .
The discount ratio dr is approximately rr , the discount predicted by the Good-Turing estimate,
and will be speci ed exactly later. The counts subtracted from the nonzero counts are thendistributed among the zero-count bigrams according to the next lower-order distribution, i.e., theunigram model. The value (wi 1 ) isPchosen so that the P
total number of counts in the distributionPii )=i ) is unchanged, i.e.,
c
(
w
c
(
w
katz
katz
i
1
i
1
wi c(wi 1 ). The appropriate value forwiwi(wi 1 ) is
(wi 1 ) =1

PP

wi :c(wii 1 )>0 pkatz (wi jwi 1 )wi :c(wii 1 )>0 pkatz (wi jwi 1 ) 1PP=1
wi :c(wii 1 )=0 pML (wi )wi :c(wii 1 )>0 pML (wi )To calculate pkatz (wi jwi 1 ) from the corrected count, we just normalize:i(wi 1 )
pkatz (wi jwi 1 ) = Pckatz
c (wi )
wi katz i 1

The dr are calculated as follows: large counts are taken to be reliable, so they are not discounted.
In particular, Katz takes dr = 1 for all r > k for some k, where Katz suggests k = 5. The discountratios for the lower counts r  k are derived from the Good-Turing estimate applied to the global
bigram distribution; that is, the nr in equation (8) denote the total numbers of bigrams that
occur exactly r times in the training data. These dr are chosen such that the resulting discounts
are proportional to the discounts predicted by the Good-Turing estimate, and such that the total
number of counts discounted in the global bigram distribution is equal to the total number of counts
that should be assigned to bigrams with zero counts according to the Good-Turing estimate.6 The
former constraint corresponds to the equations

1 dr = (1 rr )for r 2 f1; : : : ; kg for some constant . The Good-Turing estimate predicts that the total numberof counts that should be assigned to bigrams with zero counts is n0 0 = n0 nn10 = n1 , so the second
constraint corresponds to the equationkX
r=1

nr (1 dr )r = n1

The unique solution to these equations is given byr
dr = r(k+1)nk+1

n1
n1
6 In the normal Good-Turing estimate, the total number of counts discounted from n-grams with nonzero counts
happens to be equal to the total number of counts assigned to n-grams with zero counts. Thus, the normalization
constant for a smoothed distribution is identical to that of the original distribution. In Katz smoothing, Katz tries
to achieve a similar e ect except through discounting only counts r  k.

1(k+1)nk+1

12

Katz smoothing for higher-order n-gram models is de ned analogously. As we can see inequation (13), the bigram model is de ned in terms of the unigram model; in general, the Katz
n-gram model is de ned in terms of the Katz (n 1)-gram model, similar to Jelinek-Mercer
smoothing. To end the recursion, the Katz unigram model is taken to be the maximum likelihood
unigram model.
Recall that we mentioned in Section 2.2 that it is usually necessary to smooth nr when using
the Good-Turing estimate, e.g., for those nr that are very low. However, in Katz smoothing thisis not essential because the Good-Turing estimate is only used for small counts r  k, and nr isgenerally fairly high for these values of r.

2.5 Witten-Bell Smoothing

Witten-Bell smoothing (Bell, Cleary, and Witten, 1990; Witten and Bell, 1991)7 was developed forthe task of text compression, and can be considered to be an instance of Jelinek-Mercer smoothing. In particular, the nth-order smoothed model is de ned recursively as a linear interpolation
between the nth-order maximum likelihood model and the (n 1)th-order smoothed model as inequation (12):pWB (wi jwii n1 +1 ) = wii n1 +1 pML (wi jwii n1 +1 ) + (1 wii n1 +1 ) pWB (wi jwii n1 +2 )(14)

To compute the parameters wii n1 +1 for Witten-Bell smoothing, we will need to use the number of
unique words that follow the history wii n1 +1 . We will write this value as N1+ (wii n1 +1 ), formallyde ned as
N1+ (wii n1 +1 ) = jfwi : c(wii n1 +1 wi ) > 0gj(15)
The notation N1+ is meant to evoke the number of words that have one or more counts, and the is meant to evoke a free variable that is summed over. We can then assign the parameters wii n1 +1
for Witten-Bell smoothing such that8
1 wii n1 +1 =N1+ (wii n1 +1 )i
N1+ (wi n1 +1 ) + Pwi c(wii n+1 )(16)

Substituting, we can rewrite equation (14) as

pWB (wi jwii n1 +1 ) =c(wii n+1 ) + N1+ (wii n1 +1 )pWB (wi jwii n1 +2 )Pi 1iwi c(wi n+1 ) + N1+ (wi n+1 )(17)

To motivate Witten-Bell smoothing, we can interpret equation (12) as saying: with probability

wii n1 +1 we should use the higher-order model, and with probability 1 wii n1 +1 we should use

the lower-order model. It seems reasonable that we should use the higher-order model if thecorresponding n-gram occurs in the training data, and back o to the lower-order model otherwise.
Then, we should take the term 1 wii n1 +1 to be the probability that a word not observed after thehistory wii n1 +1 in the training data occurs after that history. To estimate the frequency of these
7 Witten-Bell smoothing refers to method C in these references.
8 Di erent notation is used in the original text (Bell, Cleary, and Witten, 1990). The order o in the original text
corresponds to our n 1, the escape probability eo corresponds to 1 wi 1 , qo corresponds to N1+ (wii n1 +1 ),
i n+1P
and Co corresponds to wi c(wii n+1 ).

13

novel words, imagine traversing the training data in order and counting how many times the word
following the history wii n1 +1 di ers from the words in all such previous events. The number ofsuch events is simply N1+ (wii n1 +1 ), the number of unique words that follow the history wii n1 +1 .
Equation (16) can be viewed as an approximation of this intuition.
The Good-Turing estimate provides another perspective on the estimation of the probabilityof novel words following a history. The Good-Turing estimate predicts that the probability of anevent not seen in the training data (using the notation from Section 2.2) is nN1 , the fraction ofcounts devoted to items that occur exactly once. Translating this value into the previous notation,
we getN1 (wii n1 +1 )Piwi c(wi n+1 )
where
N1 (wii n1 +1 ) = jfwi : c(wii n1 +1 wi ) = 1gj
Equation (16) can be seen as an approximation to the Good-Turing estimate, where the numberof words with at least one count is used in place of the number of words with exactly one count.
Extensive comparisons between Witten-Bell smoothing and other smoothing techniques fortext compression are presented in (Bell, Cleary, and Witten, 1990) and (Witten and Bell, 1991);
however, comparisons with smoothing techniques used in language modeling are not reported. Text
compression applications have requirements, such as the ability to build models very eciently andincrementally, that we do not consider in this work.

2.6 Absolute Discounting

Absolute discounting (Ney, Essen, and Kneser, 1994), like Jelinek-Mercer smoothing, involves theinterpolation of higher- and lower-order models. However, instead of multiplying the higher-ordermaximum-likelihood distribution by a factor wii n1 +1 , the higher-order distribution is created bysubtracting a xed discount D  1 from each nonzero count. That is, instead of equation (12):pinterp(wi jwii n1 +1 ) = wii n1 +1 pML (wi jwii n1 +1 ) + (1 wii n1 +1 ) pinterp(wi jwii n1 +2 )we havefc(wii n+1 ) D; 0g + (1  i 1 ) p (w jwi 1 )pabs (wi jwii n1 +1 ) = maxP
wi n+1 abs i i n+2c(wi )
wi

i n+1

(18)

To make this distribution sum to 1, we takeD
N1+ (wii n1 +1 )ic(wi wi n+1 )1 wii n1 +1 = P(19)

where N1+ (wii n1 +1 ) is de ned as in equation (15) and where we assume 0  D  1. Ney, Essen,
and Kneser (1994) suggest setting D through deleted estimation on the training data. They arriveat the estimate
D = n +n12n(20)
12
where n1 and n2 are the total number of n-grams with exactly one and two counts, respectively,in the training data, where n is the order of the higher-order model being interpolated.
14

We can motivate absolute discounting using the Good-Turing estimate. Church and Gale
(1991) show empirically that the average Good-Turing discount (r r ) associated with n-gramswith larger counts (r  3) is largely constant over r. Further supporting evidence is presented in
Section 5.2.1. Furthermore, the scaling factor in equation (19) is similar to the analogous factor
for Witten-Bell smoothing given in equation (16) as described in Section 2.5, and can be viewed
as approximating the same value, the probability of a novel word following a history.

2.7 Kneser-Ney Smoothing

Kneser and Ney (1995) have introduced an extension of absolute discounting where the lowerorder distribution that one combines with a higher-order distribution is built in a novel manner.
In previous algorithms, the lower-order distribution is generally taken to be a smoothed versionof the lower-order maximum likelihood distribution. However, a lower-order distribution is asigni cant factor in the combined model only when few or no counts are present in the higherorder distribution. Consequently, they should be optimized to perform well in these situations.
To give a concrete example, consider building a bigram model on data where there exists aword that is very common, say Francisco, that occurs only after a single word, say San. Sincec(Francisco) is high, the unigram probability p(Francisco) will be high and an algorithm suchas absolute discounting will assign a relatively high probability to the word Francisco occurring
after novel bigram histories. However, intuitively this probability should not be high since inthe training data the word Francisco follows only a single history. That is, perhaps the word
Francisco should receive a low unigram probability because the only time the word occurs iswhen the last word is San, in which case the bigram probability models its probability well.
Extending this line of reasoning, perhaps the unigram probability used should not be proportional to the number of occurrences of a word, but instead to the number of di erent words that it
follows. To give an intuitive argument, imagine traversing the training data in order and building
a bigram model on the preceding data to predict the current word. Then, whenever the current
bigram does not occur in the preceding data, the unigram probability will be a large factor in
the current bigram probability. If we assign a count to the corresponding unigram whenever suchan event occurs, then the number of counts assigned to each unigram will simply be the numberof di erent words that it follows. In fact, in Kneser-Ney smoothing the unigram probability in a
bigram model is calculated in this manner; however, this calculation is motivated in an entirely
di erent manner in the original paper.
The motivation given in the original text is that we should select the lower-order distribution
such that the marginals of the higher-order smoothed distribution should match the marginals of
the training data. For example, for a bigram model we would like to select a smoothed distribution
pKN that satis es the following constraint on unigram marginals for all wi :X
(21)
pKN (wi 1 wi ) = Pc(wc(i )w )
i
wi
wi 1
The left-hand side of this equation is the unigram marginal for wi of the smoothed bigram distribution pKN , and the right-hand side is the unigram frequency of wi found in the training data.
Here, we present a di erent derivation of the resulting distribution than is presented by Kneser
and Ney (1995). We assume that the model has the form given in equation (18)fc(wii n+1 ) D; 0g + P D
pKN(wi jwii n1 +1 ) = maxP
N1+ (wii n1 +1 ) pKN (wi jwii n1 +2 )
i
i
)
)
c
(
w
c
(
w
i n+1
i n+1
wi
wi
(22)
15

as opposed to the form used in the original paper8
fc(wii n+1) D;0g
< maxPii 1w c(wi n+1 )i n+1 ) = :i 1iif c(wii n+1 ) > 0(wi n+1 )pKN (wi jwii n1 +2 ) if c(wii n+1 ) = 0
where (wii n1 +1 ) is chosen to make the distribution sum to 1. That is, we interpolate the lowerorder distribution with all words, not just with words that have zero counts in the higher-order
distribution. (Using the terminology to be de ned in Section 2.8, we use an interpolated model
instead of a backo model.) We use this formulation because it leads to a cleaner derivationof essentially the same formula; no approximations are required as in the original derivation.
In addition, as will be shown later in this paper, the former formulation generally yields better
performance.
Now, our aim is to nd a unigram distribution pKN (wi ) such that the constraints given byequation (21) are satis ed. Expanding equation (21), we getc(wi ) = X p (w jw )p(w )P
KN i i 1
i 1
wi c(wi ) wi 1

pKN(wi jw

For p(wi 1 ), we simply take the distribution found in the training datap(wi 1 ) = P c(wic(w1 ) )i 1
wi 1
Substituting and simplifying, we havec(wi ) =X

wi 1c(wi 1 )pKN (wi jwi 1 )Substituting in equation (22), we have#"fc(wi 1 wi ) D; 0g + P D
N1+ (wi 1 ) pKN (wi )c(wi 1 ) maxPc(wi ) =wi c(wi 1 wi )wi c(wi 1 wi )wi 1
XXc(wi 1 ) c(wic(w1 wi ) ) D + c(wi 1 ) c(wD ) N1+ (wi 1 ) pKN (wi )
=
i 1
i 1
wi 1
wi 1 :c(wi 1 wi )>0
X= c(wi ) N1+ (wi )D + D pKN(wi )

X

wi 1

N1+ (wi 1 )

= c(wi ) N1+ (wi )D + D pKN(wi )N1+ ()where

N1+ (wi ) = jfwi 1 : c(wi 1 wi ) > 0gj
is the number of di erent words wi 1 that precede wi in the training data and whereX
X
N1+ () = N1+ (wi 1 ) = jf(wi 1 ; wi ) : c(wi 1 wi ) > 0gj = N1+ (wi )
wi

wi 1

Solving for pKN (wi ), we getwi )pKN (wi ) = NN1+ ((
)
1+

16

algorithm

additive
Jelinek-Mercer
Katz
Witten-Bellabsolute disc.
Kneser-Ney(interpolated)(wi jwii n1 +1 )(wii n1 +1 )i
P c(wi i n+1 )+
wi c(wi n+1 )+jV j
wii n1 +1 pML (wi jwii n1 +1 ) + : : :0(1 Pwii n1 +1 )

P

P

dr r
i
wi c(wi n+1 )(1 (wii n1 +1 ))pML (wi jwii n1 +1 ) + : : :maxPfc(wii n+1) D;0g + : : :iwi c(wi n+1 )imaxP
fc(wi n+1) D;0g + : : :iwi c(wi n+1 )psmooth (wi jwii n1 +2 )
n.a.

i 1
wi :c(wii n+1 )>0 pkatz (wi jwi n+1 )i 1
wi :c(wii n+1 )=0 pkatz (wi jwi n+2 )i
1
N1+ (wi Pn+1 )
N1+ (wii n1 +1 )+ wi c(wii n+1 )

1

i 1
D
i n+1 ) N1+ (wi n+1 )
c
(
w
i
wi
D
P
N1+ (wii n1 +1 )iwi c(wi n+1 )P

pinterp(wi jwii n1 +2 )pkatz (wi jwii n1 +2 )pWB (wi jwii n1 +2 )pabs (wi jwii n1 +2 )N1+ (wii n+2 )N1+ (wii n1 +2 )

Table 2: Summary of smoothing algorithms using notation from equation (24); the token \: : : "represents the term (wii n1 +1 )psmooth (wi jwii n1 +2 ) corresponding to interpolation with a lowerorder distribution
Generalizing to higher-order models, we have thatipKN (wi jwii n1 +2 ) = N1+ (wii 1n+2 )N1+ (wi n+2 )

(23)

where

N1+ (wii n+2 ) = jfwi n+1 : c(wii n+1 ) > 0gj
X
N1+ (wii n1 +2 ) = jf(wi n+1 ; wi ) : c(wii n+1 ) > 0gj = N1+ (wii n+2 )wi

2.8 Algorithm Summary

As noted by Kneser and Ney (1995), most existing smoothing algorithms can be described withthe following equation

psmooth(wi jwii n1 +1 ) =(wi jwii n1 +1 )if c(wii n+1 ) > 0i
1i
1(wi n+1 )psmooth (wi jwi n+2 ) if c(wii n+1 ) = 0(24)

That is, if an n-gram has a nonzero count then we use the distribution (wi jwii n1 +1 ). Otherwise, webacko to the lower-order distribution psmooth (wi jwii n1 +2 ), where the scaling factor (wii n1 +1 ) is
chosen to make the conditional distribution sum to one. We refer to algorithms that fall directly inthis framework as backo models. Katz smoothing is the canonical example of backo smoothing.
Several smoothing algorithms are expressed as the linear interpolation of higher- and lowerorder n-gram models as in equation (12)psmooth(wi jwii n1 +1 ) = wii n1 +1 pML (wi jwii n1 +1 ) + (1 wii n1 +1 ) psmooth(wi jwii n1 +2 )17

We can rewrite this as
psmooth(wi jwii n1 +1 ) = 0 (wi jwii n1 +1 ) + (wii n1 +1 )psmooth(wi jwii n1 +2 )where
0 (wi jwi 1 ) =  i 1 pML(wi jwi 1 )
i n+1
i n+1
wi n+1and (wii n1 +1 ) = 1 wii n1 +1 . Then, by taking(wi jwii n1 +1 ) = 0 (wi jwii n1 +1 ) + (wii n1 +1 )psmooth(wi jwii n1 +2 )(25)
we see that these models can be placed in the form of equation (24). We refer to models of thisform as interpolated models,
The key di erence between backo and interpolated models is that in determining the probability of n-grams with nonzero counts, interpolated models use information from lower-order
distributions while backo models do not. In both backo and interpolated models, lower-order
distributions are used in determining the probability of n-grams with zero counts.
In Table 2, we summarize all of the smoothing algorithms described earlier in terms of equation (24). For interpolated models, we use the notation \..." as shorthand for the last term inequation (25).
We note that it is easy to create a backo version of an interpolated algorithm. Instead ofusing equation (25), we can just take(wi jwii n1 +1 ) = 0 (wi jwii n1 +1 )and then adjust (wii n1 +1 ) appropriately so that probabilities sum to one. As described later, wehave implemented the interpolated and backo versions of several algorithms.

2.9 Other Smoothing Techniques

In this section, we brie y describe several smoothing algorithms that are not widely used, butwhich are interesting from a theoretical perspective. The algorithms in this section were not
re-implemented in this research, while all preceding algorithms were.

2.9.1 Church-Gale Smoothing

Church and Gale (1991) describe a smoothing method that like Katz's, combines the Good-Turing
estimate with a method for merging the information from lower- and higher-order models.
We describe this method for bigram models. To motivate this method, consider using theGood-Turing estimate directly to build a bigram distribution. For each bigram with count r, we
would assign a corrected count of r = (r +1) nnr+1
r . As noted in Section 2.3, this has the undesirable
e ect of giving all bigrams with zero count the same corrected count; instead, unigram frequencies
should be taken into account. Consider the corrected count assigned by an interpolative model toa bigram wii 1 with zero counts. In such a model, we would havep(wi jwi 1 ) / p(wi )for a bigram with zero counts. To convert this probability to a count, we multiply by the total
number of counts in the distribution to getp(wi jwi 1 )X

wic(wii 1 ) / p(wi )X

wic(wii 1 ) = p(wi )c(wi 1 ) / p(wi )p(wi 1 )18

Thus, p(wi 1 )p(wi ) may be a good indicator of the corrected count of a bigram wii 1 with zero
counts.
In Church-Gale smoothing, bigrams wii 1 are partitioned or bucketed by their pML (wi 1 )pML (wi )value. That is, they divide the range of possible pML (wi 1 )pML (wi ) values into a number of partitions, and all bigrams associated with the same subrange are considered to be in the same bucket.
Then, each bucket is treated as a distinct probability distribution and Good-Turing estimation is
performed within each. For a bigram in bucket b with rb counts, we calculate its corrected countrb asrb = (rb + 1) nnb;r+1
b;rwhere the counts nb;r include only those bigrams within bucket b.
Church and Gale partition the range of possible pML(wi 1 )pML (wi ) values into about 35 buckets,with three buckets in each factor of 10. To smooth the nb;r for the Good-Turing estimate, they
use a smoother by Shirey and Hastie (1988).
While extensive empirical analysis is reported, they present only a single entropy result, comparing the above smoothing technique with another smoothing method introduced in their paper,
extended deleted estimation. In our previous work (Chen, 1996), we present further results, indicating that this smoothing works well for bigram language models. When extending this method
to trigram models, there are two options for implementation. Unfortunately, one of these methods
is computationally intractable, and we have demonstrated that the other performs poorly.

2.9.2 Bayesian Smoothing

Several smoothing techniques are motivated within a Bayesian framework. A prior distribution
over smoothed distributions is selected, and this prior is used to somehow arrive at a nal smoothed
distribution. For example, Nadas (1984) selects smoothed probabilities to be their mean a posteriori value given the prior distribution.
Nadas (1984) hypothesizes a prior distribution from the family of beta functions. Nadas reports
results on a single training set indicating that Nadas smoothing performs slightly worse than Katz
and Jelinek-Mercer smoothing.
MacKay and Peto (1995) use Dirichlet priors in an attempt to motivate the linear interpolation
used in Jelinek-Mercer smoothing. They compare their method with Jelinek-Mercer smoothing ona single training set of about two million words; their results indicate that MacKay-Peto smoothing
performs slightly worse than Jelinek-Mercer smoothing.

3 Modi ed Kneser-Ney Smoothing
In this section, we introduce a novel variation of Kneser-Ney smoothing, which we refer to asmodi ed Kneser-Ney smoothing, that we have found has excellent performance. Instead of using
a single discount D for all nonzero counts as in Kneser-Ney smoothing, we have three di erent
parameters, D1 , D2 , and D3+ , that are applied to n-grams with one, two, and three or morecounts, respectively. In other words, instead of using equation (22) from Section 2.7, we takeiipKN (wi jwii n1 +1 ) = c(wi nP+1 ) c(wDi(c(wi ) n+1 )) + (wii n1 +1 )pKN (wi jwii n1 +2 )
wi

i n+1

19

where80>><

if c = 0
D
if=1
1
D(c) = > D2 if cc =2>:
D3+ if c  3

To make the distribution sum to 1, we take(wii n1 +1 ) =D1 N1 (wii n1 +1 ) + D2PN2 (wii n1 +1 ) + D3+ N3+ (wii n1 +1 )iwi c(wi n+1 )where N2 (wii n1 +1 ) and N3+ (wii n1 +1 ) are de ned analogously to N1 (wii n1 +1 ).
This modi cation is motivated by evidence to be presented in Section 5.2.1 that the ideal
average discount for n-grams with one or two counts is substantially di erent from the ideal
average discount for n-grams with higher counts. Indeed, we will see later that modi ed KneserNey smoothing signi cantly outperforms regular Kneser-Ney smoothing.
Just as Ney, Essen, and Kneser (1994) have developed an estimate for the optimal D for
absolute discounting and Kneser-Ney smoothing as a function of training data counts (as given inequation (20)), it is possible to create analogous equations to estimate the optimal values for D1 ,
D2 , and D3 (Ries, 1997). The analogous relations for modi ed Kneser-Ney smoothing are

Y = n +n12n
12n
D1 = 1 2Y n21n
D2 = 2 3Y n32n
D3+ = 3 4Y n43(26)

4 Experimental Methodology
In this section, we describe the details of our smoothing algorithm implementations, how wechose parameter values for algorithms with parameters, the data sets we used, and other aspectsof our experimental methodology. Brie y, we implemented all of the most widely-used smoothingalgorithms for language modeling: additive smoothing, Jelinek-Mercer smoothing, Katz smoothing,
Witten-Bell smoothing, absolute discounting, and Kneser-Ney smoothing. In addition, we selected
a simple instance of Jelinek-Mercer smoothing to serve as a baseline, and we implemented our
modi ed version of Kneser-Ney smoothing. We compared these smoothing algorithms using text
from the Brown corpus, the North American Business news corpus, the Switchboard corpus, andthe Broadcast News corpus.
It should be noted that there exist language modeling toolkits (Rosenfeld, 1995; Clarkson
and Rosenfeld, 1997) which can be used to build smoothed n-gram models using a variety ofsmoothing algorithms, including Katz smoothing, Jelinek-Mercer smoothing, absolute discounting,and Witten-Bell smoothing. These toolkits have found wide use, most notably in the area of speech
recognition. However, they cannot perform parameter optimization and they do not support all of
the algorithms we wanted to evaluate; thus, they were not suitable for our experiments.

20

4.1 Smoothing Implementations

In this section, we discuss the details of our implementations of various smoothing techniques;
often, the original description of an algorithm is not entirely complete and unambiguous. In
several cases, we implemented multiple variations of an algorithm when an ambiguity was present,
and chose the version that performed best.
The titles of the following sections include the mnemonic we use to refer to the implementations
in later sections. We use the mnemonic when we are referring to our speci c implementation ofa smoothing method, as opposed to the algorithm in general. For each method, we mention theparameters that can be tuned to optimize performance; in general, any variable mentioned is atunable parameter. Typically, we set parameter values to optimize the perplexity of held-out data;
for more details, refer to Section 4.2.
More details about our complete implementation, including techniques for limiting memory usage for large data sets, are given elsewhere (Chen, 1996). One observation that we take advantage
of is that for some algorithms, when optimizing the values of parameters on a held-out set, it issucient to only consider a small portion of the entire n-gram model. That is, when parametervalues change, we need only recompute the portion of the n-gram model relevant to the held-out
set. Thus, for these algorithms it is possible to perform parameter optimization eciently, while
for algorithms not falling into this category it is generally necessary to traverse the entire training
set whenever parameters are adjusted. The implementations for which parameter optimization isexpensive include all backo algorithms and the algorithm jelinek-mercer-delest; this computational cost is the reason we did not use these algorithms in some of the experiments with verylarge data sets.

4.1.1 Additive Smoothing (plus-one, plus-delta)

We consider two versions of additive smoothing. Referring to equation (7) in Section 2.1, we x

 = 1 in plus-one smoothing. In plus-delta, we consider any . (The values of parameters suchas  are determined through training on held-out data.)

To improve performance, we perform backo when a history has no counts. That is, whenc(wii n1 +1 ) = 0 we takepadd(wi jwii n1 +1 ) = padd (wi jwii n1 +2 )instead of using equation (7). Furthermore, for method plus-delta, instead of a single  we havea separate n for each level of the n-gram model.

4.1.2 Jelinek-Mercer Smoothing (jelinek-mercer, jelinek-mercer-delest)

Recall that higher-order models are de ned recursively in terms of lower-order models. We end therecursion by taking the 0th-order distribution
P to be the uniform distribution punif(wi ) = 1=jV j.
We bucket the wii n1 +1 according to wi c(wii n+1 ) as suggested by Bahl et al. Intuitively,
each bucket should be made as small as possible, to only group together the most similar n-grams,
while remaining large enough to accurately estimate the associated parameters. We make theassumption that whether a bucket is large enough for accurate parameter estimation depends only
on the number of n-grams that fall in that bucket in the data used to train the 's. We assign
buckets soPthat a minimum of cmin n-grams fall in each bucket. WeP
start from the lowest possible
value of wi c(wii n+1 ) (i.e., zero) and put increasing values of wi c(wii n+1 ) into the same
bucket until this minimum count is reached. We repeat this process until all possible values of
21

P

i
wi c(wi n+1 ) are bucketed. If the last bucket has fewer than cmin counts, we merge it with thepreceding bucket. We use separate buckets for each n-gram model being interpolated.
In performing thisP bucketing, we create an array containing the number of n-grams that occur
value, which we call ctop . For n-gramsfor each valuePof wi c(wii n+1 ) up to some maximumP
wii n1 +1 with wi c(wii n+1 ) > ctop , we pretend wi c(wii n+1 ) = ctop for bucketing purposes.
As mentioned in Section 2.3, the 's can be trained eciently using the Baum-Welch algorithm.
Given initial values for the 's, the Baum-Welch algorithm adjusts these parameters iteratively
to minimize the entropy of some data. The algorithm generally decreases the entropy with each
iteration, and guarantees not to increase it. We set all 's initially to the value 0 . We terminate
the algorithm when the entropy per word changes less than stop bits between iterations. (Notethat the parameters cmin, ctop, 0 , and stop are all considered for optimization, as are all variables
in later sections.)
We implemented two versions of Jelinek-Mercer smoothing, one using held-out interpolationand one using deleted interpolation. In jelinek-mercer, the 's are trained using held-out interpolation on a held-out set. In jelinek-mercer-delest, the 's are trained using the relaxed
deleted interpolation technique described by Jelinek and Mercer, where one word is deleted at atime. (This is also known as the leave-one-out method.) In jelinek-mercer-delest, we bucket
an n-gram according to its count before deletion, as this turned out to signi cantly improve performance. We hypothesize that this is because an n-gram is then placed in the same bucket during
training as in evaluation, allowing the 's to be meaningfully geared toward individual n-grams.

4.1.3 Katz Smoothing (katz)

Referring to Section 2.4, instead of a single k we allow a di erent kn for each n-gram model beingcombined.
Recall that higher-order models are de ned recursively in terms of lower-order models, andthat the recursion is ended by taking the unigram distribution to be the maximum likelihood distribution. While using the maximum likelihood unigram distribution often works well in practice,
this choice is not well-suited to our work. In practice, the vocabulary V is usually chosen to include only those words that occur in the training data, so that pML(wi ) > 0 for all wi 2 V . Thisassures that the probabilities of all n-grams are nonzero. However, in this work not all words inthe vocabulary always occur in the training data. We run experiments using many training set
sizes, and we use a xed vocabulary across all runs so that results between sizes are comparable.
Not all words in the vocabulary will occur in the smaller training sets. Thus, unless we smooth
the unigram distribution we may have n-gram probabilities that are zero, which could lead to anin nite cross-entropy on test data. To address this issue, we smooth the unigram distribution in
Katz smoothing using additive smoothing; we call the additive constant .9
In the algorithm as described in the original paper, no probability is assigned to n-gramswith zero counts in a conditional distribution p(wi jwii n1 +1 ) if there are no n-grams wii n+1 that
occur between 1 and kn times in that distribution. This can lead to an in nite cross-entropy
on test data. To address this, whenever there are no counts between 1 and kn in a conditional
distribution, we give the zero-count n-grams a total of counts, and increase the normalization
constant appropriately.
9 In Jelinek-Mercer smoothing, we address this issue by ending the model recursion with a 0th-order model insteadof a unigram model, and taking the 0th-order model to be a uniform distribution. We tried a similar tack withKatz smoothing, but applying the natural extension of the Katz algorithm to combining a unigram and uniform
model led to poor results. We tried additive smoothing instead, which is equivalent to interpolating with a uniform
distribution using the Jelinek-Mercer paradigm, and this worked well.

22

4.1.4 Witten-Bell Smoothing (witten-bell-interp, witten-bell-backoff)

The implementation witten-bell-interp is a faithful implementation of the original algorithm,
where we end the model recursion by taking the 0th-order distribution to be the uniform distribution. The implementation witten-bell-backoff is a backo version of the original algorithm(see Section 2.8).

4.1.5 Absolute Discounting (abs-disc-interp, abs-disc-backoff)

Referring to Section 2.6, instead of a single D over the whole model we use a separate Dn foreach n-gram level. As usual, we terminate the model recursion with the uniform distribution.
Also, instead of using equation (20) to calculate Dn , we nd the values of Dn by optimizing the
perplexity of held-out data. The implementation abs-disc-backoff is a backo version of absdisc-interp(see Section 2.8).

4.1.6 Kneser-Ney Smoothing (kneser-ney, kneser-ney-fix)

Referring to Section 2.7, instead of taking equation (23) as is, we smooth lower-order distributions
in a similar fashion as the highest-order distribution. That is, for all n-gram models below thehighest level we takefN1+(wii n+1 ) D; 0g + P
D
N1+ (wii n1 +1 ) pKN (wi jwii n1 +2 )pKN (wi jwii n1 +1 ) = maxP
i
i
)
)
N
(
w
N
(
w
wi 1+ i n+1
wi 1+ i n+1
We end the model recursion by taking the 0th-order distribution to be the uniform distribution.
Also, instead of a single D over the whole model we use a separate Dn for each n-gram level. The
algorithm kneser-ney sets the Dn parameters by optimizing the perplexity of held-out data. The
method kneser-ney-fix sets the Dn parameters using equation (20) as suggested in the original
paper.

4.1.7 Modi ed Kneser-Ney Smoothing (kneser-ney-mod, kneser-ney-mod-fix, kneserney-mod-backoff)
The implementation kneser-ney-mod of modi ed Kneser-Ney smoothing (Section 3) is identical tothe implementation kneser-ney, with the exception that three discount parameters, Dn;1 , Dn;2 ,and Dn;3+ , are used at each n-gram level instead of just a single discount Dn .
The algorithm kneser-ney-mod-fix is identical to kneser-ney-mod, except that the discountparameters are set using equation (26) instead of by being optimized on held-out data. The
implementation kneser-ney-mod-backoff is the backo version of the interpolated algorithm
kneser-ney-mod.

4.1.8 Baseline Smoothing (jelinek-mercer-baseline)

For our baseline smoothing method, we use a version of Jelinek-Mercer smoothing with held-out
interpolation. Speci cally, for each n-gram model being interpolated we constrain all wii n1 +1 inequation (12) to be equal to a single value n . We make an exception when the history wii n1 +1
has never occurred in the training data, in which case we take wii n1 +1 to be zero as there is no23

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

performance of katz with respect to delta
100 sent

1.4
1.2
1
0.8

1000 sent
0.6
0.4
0.2
0
45000 sent

-0.2
-0.4
0.001

0.01

0.1

1

10

100

delta

performance of jelinek-mercer with respect to c-min
-0.04
-0.05
10000000 sent

-0.06
-0.07
-0.08
-0.09

1000000 sent

-0.1

10000 sent
1

10
100
1000
10000
minimum number of counts per bucket

Figure 1: Performance relative to baseline algorithm jelinek-mercer-baseline of algorithms
 and cmin, respectively, over several training
set sizes

katz and jelinek-mercer with respect to parametersinformation in the higher-order distribution. This is identical to jelinek-mercer where cmin is
set to 1, so that there is only a single bucket (for nonzero counts) for each n-gram level.10

4.2 Parameter Setting

In this section, we discuss how the setting of smoothing parameters a ects performance, andexamine which parameters a ect overall performance signi cantly. In Figure 1, we give a coupleof examples of the sensitivity of smoothing algorithms to parameter values: we show how thevalue of the parameter  (which controls unigram smoothing) a ects the performance of the katz
algorithm, and how the value of the parameter cmin (which determines bucket size) a ects theperformance of jelinek-mercer. Notice that poor parameter setting can lead to very signi cantlosses in performance. In Figure 1, we see di erences in entropy from several hundredths of a bit toover a bit. Also, we see that the optimal value of a parameter varies with training set size. Thus,
it is important to optimize parameter values to meaningfully compare smoothing techniques, andthis optimization should be speci c to the given training set.
In each of our experiments, optimal values for the parameters of each method were searched
for using Powell's search algorithm (Press et al., 1988). Parameters were chosen to optimize thecross-entropy of a held-out set associated with each training set. More speci cally, as describedin Section 4.3 there are three held-out sets associated with each training set, and parameter
optimization was performed using the rst of the three.
For instances of Jelinek-Mercer smoothing, the 's were trained using the Baum-Welch algorithm on the second of the three held-out sets; all other parameters were optimized using Powell'salgorithm on the rst set. In particular, to evaluate the entropy associated with a given set of(non-) parameters in Powell's search, we rst optimize the 's on the second held-out set.
10 This description di ers from the description of the baseline algorithm given in our previous work (Chen andGoodman, 1996; Chen, 1996). In the other texts, we do not describe an exception for the case where the history
has never occurred and always set wi 1 to n . However, the other descriptions are inaccurate: the description
i n+1
presented here applies to all of the work.

24

algorithm
plus-oneplus-deltajelinek-mercer
jelinek-mercer-delest

katz11
witten-bell-interp
witten-bell-backoff
abs-disc-interp
abs-disc-backoff
kneser-ney
kneser-ney-fix
kneser-ney-mod
kneser-ney-mod-backoff
kneser-ney-mod-fix
jelinek-mercer-baseline

signi cant parameters insigni cant parameters
none
none
n
none
wii n1 +1 , cmin
0 = 0:5, stop = 0:001, ctop = 100; 000
wii n1 +1 , cmin
0 = 0:5, stop = 0:001, ctop = 100; 000kn = knmax, = 1
none
none
none
none
Dn
none
Dn
none
Dn
none
none
none
Dn;1 , Dn;2, Dn;3+
none
Dn;1 , Dn;2, Dn;3+
none
none
none
n
0 = 0:5, stop = 0:001

Table 3: Parameters that signi cantly a ect perplexity for each smoothing algorithm, and insignificant parameters and their default values
To constrain the parameter search in our main experiments, we searched only those parametersthat were found to a ect performance signi cantly, as indicated through preliminary experiments
over several data sizes. In each run of these preliminary experiments, we xed all (non-) parameters but one to some reasonable value, and used Powell's algorithm to search on the single freeparameter. If the range of test data entropies over all parameter values considered by Powell'salgorithm was much smaller than the typical di erence in entropies between di erent algorithms(i.e., 0.005 bits), we chose not to perform the search over this parameter in the later experiments,and simply assign an arbitrary reasonable value to the parameter. For each parameter, we tried
three di erent training sets: 20,000 words from the WSJ corpus, one million words from the Brown
corpus, and three million words from the WSJ corpus.
We summarize the results of these experiments in Table 3; Chen (1996) gives more details. For
each algorithm, we list the parameters we found to be signi cant (and thus search over in eachlater experiment); we also list the insigni cant parameters and the value we set them to.

4.3 Data

We used data from the Brown corpus, the North American Business news corpus, the Switchboard
corpus, and the Broadcast News corpus.12
The text of the Brown corpus (Kucera and Francis, 1967) was extracted from the tagged text
in the Penn Treebank (Marcus, Santorini, and Marcinkiewicz, 1993) and amounted to about one
million words. The vocabulary we used with the Brown corpus experiments is the set of all 53,850
11 We found that the larger the value of each kn , the better the performance. However, for large kn there will becounts r such that the associated discount ratio dr takes on an unreasonable value, such as a nonpositive value ora value above one. We take kn to be as large as possible such that all dr take on reasonable values.
12 All of this data is available from the Linguistic Data Consortium.

25

words occurring in the corpus. The average sentence length is about 21 words.
The North American Business news text was taken from the language modeling data distributed
for the 1995 ARPA continuous speech recognition evaluation (Stern, 1996). The data included 110
million words of Associated Press (AP) text, 98 million words of Wall Street Journal (WSJ) text,
and 35 million words of San Jose Mercury News (SJM) text. For these experiments, we used the
20,000 word vocabulary supplied for the evaluation. We primarily used the Wall Street Journal
text, and only used the other text if more than 98 million words of data was required. We referto this data as the WSJ/NAB corpus. The average sentence lengths for the Wall Street Journal,
Associated Press, and San Jose Mercury News texts are about 23, 22, and 20 words, respectively.
The Switchboard data is three million words of telephone conversation transcriptions (Godfrey,
Holliman, and McDaniel, 1992). The version of the data we used was processed by the Janus
speech recognition group (Rogina and Waibel, 1995), and in our experiments we used their 9,800
word vocabulary. The average sentence length is about 16 words.
The Broadcast News text was taken from the language modeling data distributed for the 1996
DARPA Hub 4 continuous speech recognition evaluation (Rudnicky, 1996). The data consists of
130 million words of transcriptions of television and radio news shows. For these experiments, weused the 50,000 word vocabulary developed by the Sphinx speech recognition group (Placeway etal., 1997) for the evaluation. The average sentence length is about 15 words.
For each experiment, we selected three segments of held-out data along with the segment oftraining data. These four segments were chosen to be adjacent in the original corpus and disjoint,
the held-out segments following the training. The rst two held-out segments were used to selectthe parameters of each smoothing algorithm, and the last held-out segment was used as the test
data for performance evaluation. The reason that two segments were reserved for parameterselection instead of one is described in Section 4.2. For experiments over multiple training set
sizes, the di erent training sets share the same held-out sets. In experiments with multiple runson the same training set size, the data segments of each run are completely disjoint.
Each piece of held-out data was chosen to be 2,500 sentences, or roughly 50,000 words. Thisdecision does not necessarily re ect practice well. For example, if the training set size is less than
50,000 words then it is not realistic to have this much held-out data available. However, we madethis choice to avoid considering the training versus held-out data tradeo for each data size. In
addition, the held-out data is used to optimize typically very few parameters, so in practice smallheld-out sets are generally adequate, and perhaps can be avoided altogether with techniques suchas deleted estimation. Another technique is to use some held-out data to nd smoothing parametervalues, and then to fold that held-out data back into the training data and to rebuild the models.
To give some avor about how the strategy used to select a held-out set a ects performance,
we ran two small sets of experiments investigating how held-out set size and how folding back theheld-out set into the training set a ects cross-entropy. In Figure 2, we display the e ect of held-out
set size on the performance of two smoothing algorithms, jelinek-mercer and kneser-ney-mod,
over three training set sizes on the Broadcast News corpus. Performance is calculated relative
to the cross-entropy yielded by using a 2,500 sentence (about 50,000 word) held-out set for thattraining set size. For jelinek-mercer smoothing, which can have hundreds of  parameters or
more, the size of the held-out set can have a moderate e ect. For held-out sets much smaller thanthe baseline size, test cross-entropy can be up to 0.03 bits/word higher, which is approximately
equivalent to a 2% perplexity di erence. However, even when the held-out set is a factor of fourlarger than the baseline size of 2,500 sentences, we see an improvement of at most 0.01 bits/word.
As we will see later, these di erences are much smaller than the typical di erence in performance
between smoothing algorithms. For kneser-ney-mod smoothing which has about 10 parameters,
held-out set size has little e ect, typically less than 0.005 bits/word.
26

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

performance of jelinek-mercer over varying held-out set sizes
5000 train sent
0.03

0.02

0.01

0

500000 train sent

-0.01

50000 train sent

100

1000
held-out set size (sentences)

10000

performance of kneser-ney-mod over varying held-out set sizes
0.008

5000 train sent

0.006
0.004
0.002
0

500000 train sent
50000 sent

-0.002100

1000
held-out set size (sentences)

10000

performance of jelinek-mercer over varying held-out set strategies

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

Figure 2: Performance relative to baseline held-out set size (2,500 sentences) of jelinek-mercer
and kneser-ney-mod over several held-out set sizes; held-out set is used to optimize smoothingalgorithm parameters

0
-0.2
-0.4

fold-back

-0.6
-0.8
-1

extra

1000

10000
100000training data (sentences)

1e+06

performance of kneser-ney-mod over varying held-out set strategies
0-0.2

fold-back
extra

-0.4
-0.6
-0.8
-1
1000

10000
100000training data (sentences)

1e+06

Figure 3: Performance relative to baseline held-out methodology of jelinek-mercer andkneser-ney-mod; fold-back corresponds to case where held-out set used to optimize parameters islater folded back into training set; extra corresponds to case where training set is augmented byoriginal held-out set, but additional held-out set is used to optimize parameters

27

In Figure 3, we display how folding back the held-out set into the training set after smoothing
parameter optimization a ects performance over di erent training set sizes for jelinek-mercer
and kneser-ney-mod. Performance is calculated relative to the cross-entropy of our default
methodology of not folding the held-out set back into the training set after parameter optimization. The fold-back line corresponds to the case where we fold the held-out data back into thetraining, and the extra line corresponds to the case where after folding the held-out data back into
the training, we use an additional held-out set to re-optimize the smoothing parameters. As would
be expected, for small training set sizes performance is augmented signi cantly when the held-out
data is folded back in, as this increases the training set size noticeably. However, for training set
sizes of 100,000 sentences or more, this improvement becomes negligible. The di erence between
the fold-back and extra lines represents the bene t of using a held-out set disjoint from the training set to optimize parameters. This bene t is insigni cant for kneser-ney-mod, but is larger for
jelinek-mercer, especially for smaller training sets.

5 Results
In this section, we present the results of our main experiments. In Section 5.1, we present theperformance of various algorithms for di erent training set sizes on di erent corpora for bothbigram and trigram models. We demonstrate that the relative performance of di erent smoothing
methods can vary signi cantly as conditions vary; however, Kneser-Ney smoothing and variations
consistently outperform all other methods.
In Section 5.2, we present a more detailed analysis of performance, rating di erent techniques
on how well they perform on n-grams with a particular count in the training data, e.g., n-grams
that have occurred exactly once in the training data. We nd that katz most accurately smooths
n-grams with large counts, while kneser-ney-mod is best for small counts. We then show the
relative impact on performance of small counts and large counts for di erent training set sizes andn-gram orders, and use this data to explain the variation in performance of di erent algorithms indi erent situations.
In Section 5.3, we present experiments with 4-gram and 5-gram models, with n-gram models
with count cuto s (i.e., models that ignore n-grams with fewer than some number of counts in the
training data), and experiments that examine how cross-entropy is related to word-error rate inspeech recognition.

5.1 Overall Results

As mentioned earlier, we evaluate smoothing methods through their cross-entropy on test data, as
given in equation (6). In Figures 4 and 5, we display the cross-entropy of our baseline smoothing
method, jelinek-mercer-baseline, over a variety of training set sizes for both bigram andtrigram models on all four corpora described in Section 4.3. We see that cross-entropy decreases
steadily as the training set used grows in size; this decrease is somewhat slower than linear in thelogarithm of the training set size. Furthermore, we see that the entropies of di erent corpora canbe very di erent, and that trigram models perform signi cantly better than bigram models only
for larger training sets.
In the following discussion, we will primarily report the performance of a smoothing algorithm
as the di erence of its cross-entropy on a test set from the cross-entropy of jelinek-mercerbaseline with the same training set. To see how these cross-entropy di erences translate to28

cross-entropy of baseline for WSJ/NAB corpus

cross-entropy of baseline for Broadcast News corpus
11.5

cross-entropy of test data (bits/token)

cross-entropy of test data (bits/token)

11
10.5
10
9.5
9
8.5
8

NAB 2-gram

7.5
7
1000

10000
100000
1e+06
training set size (sentences)

10
9.5
9
8.5
8

BN 2-gram

7.5
7

NAB 3-gram
6.5
100

11
10.5

1e+07

BN 3-gram

100

1000

10000
100000training set size (sentences)

1e+06

Figure 4: Cross-entropy of baseline algorithm jelinek-mercer-baseline on test set over various
training set sizes on WSJ/NAB and Broadcast News corpora
cross-entropy of test data (bits/token)

cross-entropy of baseline for Brown and Switchboard corpora
10
9.5
9
8.5

Brown 2-gram
Brown 3-gram

8
7.5

SWB 2-gram
7
6.5
100

SWB 3-gram
1000
10000
training set size (sentences)

100000Figure 5: Cross-entropy of baseline algorithm jelinek-mercer-baseline on test set over various
training set sizes on Brown and Switchboard corpora

29

perplexity, recall that perplexity PPm (T ) is related to cross-entropy Hm (T ) as
PPm (T ) = 2Hm (T )Hence, xed di erences in cross-entropy are equivalent to xed ratios in perplexity. For example, a
1% decrease in perplexity is equivalent to a log2 (1 0:01)  0:014 bits/word decrease in entropy,
and a 10% decrease in perplexity is equivalent to a log2 (1 0:1)  0:152 bits/word decrease inentropy.
Unless noted, all of the points in each graph represent a single run on a single training and test
set. To give some idea about the magnitude of the error in our results, we ran a set of experiments
where for each training set size, we ran ten experiments on completely disjoint data sets (training
and test). We calculated the empirical mean and the standard deviation (of the mean) over theseten runs; these values are displayed in Figures 6 and 7. In Figure 6, we display the absolute crossentropy of the baseline algorithm, jelinek-mercer-baseline, on the Switchboard and Broadcast
News corpora for bigram and trigram models over a range of training set sizes. The standard
deviation on the Switchboard runs was very small; on Broadcast News, the variation was relatively
large, comparable to the di erences in performance between smoothing algorithms. In Figure 7,
we display the performance of a number of smoothing algorithms relative to the baseline algorithm
on the Broadcast News and Switchboard corpora for trigram models on a range of training set
sizes. We see that the variation in cross-entropy relative to the baseline is generally fairly small,much smaller than the di erence in performance between algorithms. Hence, while the variationin absolute cross-entropies is large, the variation in relative cross-entropies is small and we canmake meaningful statements about the relative performance of algorithms in this domain.
However, in later graphs each point will represent a single run instead
p of an average over ten
runs, and the standard deviation for a single run will be a factor of about 10 larger than the valuesplotted in Figure 7. With these larger deviations, the relative performance of two algorithms withsimilar performance may be dicult to determine from a single pair of points. However, we believethat an accurate and precise picture of relative performance can be gleaned from the graphs to bepresented later due to the vast overall number of experiments performed: most experiments arecarried out over a variety of training set sizes and on each of four independent corpora. Relative
performance trends are largely consistent over these runs. Nevertheless, there is one phenomenon
that seems to adversely and signi cantly a ect the performance of a certain group of algorithms
on a small number of data sets, e.g., see the points corresponding to a training set size of 30,000
sentences in the graphs in Figure 10. We present an analysis of this anomaly in Section 5.1.1; thealgorithms that this phenomenon a ects correspond to the algorithms with the largest variance inFigure 7.

5.1.1 Overall Performance Di erences

In Figures 8{11, we display the performance of various algorithms relative to the baseline algorithm
jelinek-mercer-baseline over a variety of training set sizes, for bigram and trigram models,and for each of the four corpora described in Section 4.3. These graphs do not display all of
the algorithms we implemented, as placing all of the algorithms on a single graph would leadto too much clutter; instead, the algorithms chosen are meant to give an overall picture of therelative performance of di erent algorithms. Comparisons between the displayed algorithms andthe algorithms omitted from the graphs are provided in following sections.
From these graphs, we see that the methods kneser-ney and kneser-ney-mod consistently
outperform all other algorithms, over all training set sizes and corpora, and for both bigram andtrigram models. These methods also outperform all algorithms not shown in the graphs, except
30

cross-entropy of baseline for Switchboard and Broadcast News corpora

cross-entropy of test data (bits/token)

11
10.5
10
9.5
9
8.5
8

BN 2-gram

7.5

SWB 2-gram
SWB 3-gram

7100

BN 3-gram

1000
10000
100000training set size (sentences)

relative performance of algorithms on Broadcast News corpus, trigram
0.1

abs-disc-interp

0.05
0baseline
katz

-0.05
jelinek-mercer
-0.1
-0.15
-0.2
100

kneser-ney-fix
kneser-ney-mod

1000
10000
100000training set size (sentences)difference in test cross-entropy from baseline (bits/token)

difference in test cross-entropy from baseline (bits/token)

Figure 6: Cross-entropy of baseline algorithm jelinek-mercer-baseline on test set over various
training set sizes on Switchboard and Broadcast News corpora; each point displays mean andstandard deviation over ten runs on disjoint data sets
relative performance of algorithms on Switchboard corpus, trigram
0.05
abs-disc-interp
0jelinek-mercer-baseline

-0.05
-0.1

kneser-ney-fix

katz

jelinek-mercer

-0.15
-0.2
100

kneser-ney-mod
1000
training set size (sentences)

10000

Figure 7: Performance relative to baseline of various algorithms on Broadcast News and Switchboard corpora, trigram model; each point displays mean and standard deviation over ten runs on
disjoint data sets31

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

relative performance of algorithms on WSJ/NAB corpus, 2-gram
0.1
0.05

abs-disc-int

witten-bell-backoff
jelinek-mercer-baseline

0
-0.05

j-m

-0.1
katz

-0.15
-0.2

kneser-ney-mod

k-n

-0.25
100

1000

10000
100000
1e+06
training set size (sentences)

1e+07

0.1

relative performance of algorithms on WSJ/NAB corpus, 3-gramabs-disc-interp
witten-bell-backoff

0.05
jelinek-mercer-baseline

0
-0.05
j-m

-0.1

kneser-ney

-0.15
-0.2

katz

kneser-ney-mod

-0.25
-0.3
100

1000

10000
100000
1e+06
training set size (sentences)

1e+07

relative performance of algorithms on Broadcast News corpus, 2-gram
0.1
witten-bell-backoff
0.05
jelinek-mercer-baseline0

abs-disc-interp
-0.05
j-m
-0.1

katz
kneser-ney-0.15
kneser-ney-mod
-0.2
100

1000

10000
100000training set size (sentences)

1e+06

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

Figure 8: Performance relative to baseline of various algorithms on WSJ/NAB corpus over various
training set sizes, bigram and trigram models
relative performance of algorithms on Broadcast News corpus, 3-gram
0.1
witten-bell-backoff
abs-disc-interp
0.05
0baseline

-0.05

katz

-0.1

jelinek-mercer-0.15

kneser-ney-0.2
kneser-ney-mod

-0.25
-0.3
100

1000

10000
100000training set size (sentences)

1e+06

Figure 9: Performance relative to baseline of various algorithms on Broadcast News corpus overvarious training set sizes, bigram and trigram models

32diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

relative performance of algorithms on Switchboard corpus, 2-gram
0.1
witten-bell-backoff
0.05
jelinek-mercer-baseline0

abs-disc-interp

-0.05
-0.1

j-m
kneser-ney katz

-0.15
-0.2

kneser-ney-mod

100

1000
10000
training set size (sentences)

100000relative performance of algorithms on Switchboard corpus, 3-gram
0.1
witten-bell-backoff
0.05
0
-0.05

baseline
abs-disc-interp
katz
jelinek-mercer

-0.1
-0.15

kneser-ney-0.2

kneser-ney-mod

-0.25
100

1000
10000
training set size (sentences)

1000000.1

relative performance of algorithms on Brown corpus, 2-gramwitten-bell-backoff

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

Figure 10: Performance relative to baseline of various algorithms on Switchboard corpus overvarious training set sizes, bigram and trigram models

0.05
jelinek-mercer-baseline

0
-0.05
-0.1

abs-disc-interp-0.15
jelinek-mercer-0.2
kneser-ney

-0.25
-0.3

katz

kneser-ney-mod

100

1000
10000
training set size (sentences)

0.1

relative performance of algorithms on Brown corpus, 3-gramwitten-bell-backoff

0.05
jelinek-mercer-baseline0

abs-disc-interp

-0.05
katz
-0.1
-0.15

jelinek-mercer-0.2

kneser-ney

-0.25
-0.3

kneser-ney-mod

-0.35
100

1000
10000
training set size (sentences)

Figure 11: Performance relative to baseline of various algorithms on Brown corpus over various
training set sizes, bigram and trigram models

33

for other variations of Kneser-Ney smoothing. In Section 5.2, we will show that this excellent
performance is due to the modi ed backo distributions that Kneser-Ney smoothing employs, as
described in Section 2.7.
The algorithms katz and jelinek-mercer generally yield the next best performance. Bothperform signi cantly better than the baseline method in almost all situations, except for cases withvery little training data. The algorithm jelinek-mercer performs better than katz in sparse
data situations, and the reverse is true when there is much data. For example, katz performs
better on Broadcast News and WSJ/NAB trigram models for training sets larger than 50,000{
100,000 sentences; for bigram models the cross-over point is generally lower. In Section 5.2, wewill explain this variation in performance relative to training set size by showing that katz is betterat smoothing larger counts; these counts are more prevalent in larger data sets.
The worst of the displayed algorithms (not including the baseline) are the algorithms absdisc-interpand witten-bell-backoff. The method abs-disc-interpgenerally outperforms
the baseline algorithm, though not for very small data sets. The method witten-bell-backoff
performs poorly, much worse than the baseline, for smaller data sets. Both of these algorithms
are signi cantly superior to the baseline for very large data sets; in these situations, they arecompetitive with the algorithms katz and jelinek-mercer.
These graphs make it apparent that the relative performance of smoothing techniques can vary
dramatically over training set size, n-gram order, and training corpus. For example, the method
witten-bell-backoff performs atrociously for small training sets but competitively on very large
training sets. There are numerous instances where the relative performance of two methods reverse
over di erent training set sizes, and this cross-over point will vary widely over n-gram order or
corpus. Thus, it is not sucient to run experiments on one or two data sets for a single training
set size to reasonably characterize the performance of a smoothing algorithm, as is the typicalmethodology in previous work.

Analysis of Performance Anomaly In the graphs in Figure 10, we see that several algorithms

behave anomalously on the training set of 30,000 sentences. The algorithms abs-disc-interp,
katz, and kneser-ney all perform substantially worse than would be expected given their performance on other training sets for both bigram and trigram models, while the remaining algorithms
seem to be una ected. As can be seen later in Figures 19 and 21, the algorithms kneser-ney-fix
and kneser-ney-mod-fix are also adversely a ected. In this section, we analyze this phenomenon
and show that this particular training set is indeed unusual, and explain why only the listed
algorithms are a ected.
After investigation, we found that the 30,000-sentence training set had an unusual distributionof counts; there were abnormally few trigrams with one count as compared to trigrams with higher
counts.13 In Figure 12, we plot the ratio of the number of trigrams with various counts to thenumber of trigrams with exactly one count over various training set sizes on the Switchboard
corpus. This graph makes apparent the unusual count distribution present in the given training
set.
This observation can be used to explain why the algorithms katz, kneser-ney-fix, andkneser-ney-mod-fix all perform unusually poorly. These algorithms share the property that
discounts are calculated based on the counts of n-grams with a particular count in the training
data. Since the training set has an unusual distribution of these counts and presumably the test
set has a more typical distribution, we have a mismatch between the training and test set, anddiscounts are not set suitably for the test set. Indeed, in Figures 19 and 21 we see that the
13 Further examination revealed that this paucity of one counts was present because a long segment of text was
duplicated in the training set.

34

n2/n1

0.4
0.35
0.3
0.25
0.2
0.15
0.1

n3/n1
0.05
0
100

n4/n1
1000
10000
training set size (sentences)

100000Figure 12: Ratio of the number of trigrams with various counts to the number of trigrams withexactly one count over various training set sizes on the Switchboard corpus
algorithms kneser-ney and kneser-ney-mod perform substantially better than kneser-ney-fix
and kneser-ney-mod-fix, respectively, on this training set. For kneser-ney and kneser-neymod, discount parameters are set through optimization on held-out data, so the mismatch between
training and test data has little e ect. This example highlights the additional robustness possible
when using held-out data to set parameters instead of setting them deterministically from trainingdata.
To explain why the algorithms abs-disc-interpand kneser-ney perform poorly on this training set, we refer to the optimal discounts calculated on the held-out set for kneser-ney-mod
smoothing for a trigram model. We nd that these discounts are spread unusually far apart forthe 30,000-sentence training set: we nd (D1 ; D2 ; D3+ ) values of about (0.9, 1.8, 2.4) when valuesof about (0.9, 1.5, 2.1) is what would be expected from interpolating the values found on training
sets of nearby size. This indicates that the ideal average discount for di erent counts on this training set are unusually spread apart, and so using a single discount D for all counts as is done by
abs-disc-interpand kneser-ney is an unusually poor approximation on this training set. Thus,
we can see how the atypical nature of the training set leads to poor performance for abs-discinterpand kneser-ney.
It is interesting to note why the algorithms jelinek-mercer, jelinek-mercer-baseline, andkneser-ney-mod do not exhibit anomalous behavior on the 30,000-sentence training set. Because
the algorithms jelinek-mercer and jelinek-mercer-baseline do not utilize the counts of ngrams with certain counts in the training data, they are una ected by the unusual distribution ofthese counts. The algorithm kneser-ney-mod retains its performance because of a combination of
two reasons: parameters are optimized on held-out data so that the mismatch between the training
and test data can be compensated for, and it has enough discount parameters to adequately
compensate for the mismatch.

5.1.2 Additive Smoothing

In Figure 13, we display the performance of the plus-one and plus-delta algorithms relative to the baseline algorithm jelinek-mercer-baseline for bigram and trigram models on the
WSJ/NAB corpus over a range of training set sizes. In general, these algorithms perform muchworse than the baseline algorithm, except for situations with a wealth of data. For example,
35diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

relative performance of algorithms on WSJ/NAB corpus, 2-gram
3.5
plus-one
3
2.5
2
1.5
plus-delta
1
0.5
0jelinek-mercer-baseline

100

1000

10000
100000
1e+06
training set size (sentences)

1e+07

relative performance of algorithms on WSJ/NAB corpus, 3-gramplus-one
4

3
plus-delta

2

1

0
100

jelinek-mercer-baseline
1000

10000
100000
1e+06
training set size (sentences)

1e+07

Figure 13: Performance relative to baseline of plus-one and plus-delta algorithms on WSJ/NAB
corpus, bigram and trigram models
plus-delta is competitive with the baseline method when using a training set of 10,000,000 sentences for a bigram model on WSJ/NAB data. Though not shown, these algorithms have similar
performance on the other three corpora. Gale and Church (1990; 1994) further discuss the performance of these algorithms.

5.1.3 Backo vs. Interpolation

In this section, we compare the performance between the backo and interpolated versions of several
smoothing algorithms. (For the de nitions of these types of models, refer to Section 2.8.) We implemented three pairs of algorithms that di er only in the backo strategy used: witten-bell-interp
and witten-bell-backoff, abs-disc-interpand abs-disc-backoff, and kneser-ney-mod andkneser-ney-mod-backoff.
In Figure 14, we display the performance of witten-bell-interp and witten-bell-backoff
relative to the baseline algorithm jelinek-mercer-baseline for bigram and trigram models on
the WSJ/NAB corpus over a range of training set sizes. We see that witten-bell-backoff
consistently outperforms witten-bell-interp over all training set sizes and for both bigram andtrigram models. While not shown, these algorithms have similar performance on the other three
corpora.
In Figures 15 and 16, we display the performance of the backo and interpolated versionsof absolute discounting and modi ed Kneser-Ney smoothing for bigram and trigram models on
the WSJ/NAB and Broadcast News corpora over a range of training set sizes. We see thatkneser-ney-mod consistently outperforms kneser-ney-mod-backoff. On small data sets, absdisc-interpoutperforms abs-disc-backoff, and the reverse holds for large data sets. We seethat the cross-over point varies with corpus and n-gram order. While not shown, these algorithms
have similar performance on the other two corpora. In Section 5.2, we present an analysis thatpartially explains the relative performance of backo and interpolated algorithms.

36diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

relative performance of algorithms on WSJ/NAB corpus, 2-gram
0.35
0.3
0.25
0.2
0.15
0.1
witten-bell-interp

0.05

jelinek-mercer-baseline

0
-0.05
100

witten-bell-backoff
1000

10000
100000
1e+06
training set size (sentences)

1e+07

relative performance of algorithms on WSJ/NAB corpus, 3-gram
0.5

witten-bell-interp

0.4
0.3
0.2
witten-bell-backoff
0.1
0jelinek-mercer-baseline

-0.1
100

1000

10000
100000
1e+06
training set size (sentences)

1e+07

Figure 14: Performance relative to baseline of witten-bell-backoff and witten-bell-interp
algorithms on WSJ/NAB corpus, bigram and trigram models

5.1.4 Kneser-Ney Smoothing and Variations

In this section, we compare the performance of the di erent variations of Kneser-Ney smoothingthat we implemented: kneser-ney, kneser-ney-mod, kneser-ney-fix, and kneser-ney-modfix. We do not discuss the performance of method kneser-ney-mod-backoff here, as this waspresented in Section 5.1.3.
In Figure 17, we display the performance of kneser-ney and kneser-ney-mod relative to thebaseline algorithm jelinek-mercer-baseline for bigram and trigram models on the WSJ/NAB
corpus over a range of training set sizes. Recall that these algorithms di er in that for each ngram level, kneser-ney has a single discount Dn for each count while kneser-ney-mod has three
discounts Dn;1 , Dn;2 , and Dn;3+ for n-grams with one count, two counts, and three or more counts,
respectively, as described in Section 4.1. We see that kneser-ney-mod consistently outperforms
kneser-ney over all training set sizes and for both bigram and trigram models. While not shown,these algorithms have similar behavior on the other three corpora. Their di erence in performanceis generally signi cant, though is smaller for very large data sets. In Section 5.2, we explain thisdi erence by showing that the correct average discount for n-grams with one count or two counts
deviates signi cantly from the correct average discount for larger counts.
In Figures 18 and 19, we display the performance of kneser-ney and kneser-ney-fix forbigram and trigram models on the WSJ/NAB and Switchboard corpora over a range of training
set sizes. Recall that these algorithms di er in that for kneser-ney we set the parameters Dn by
optimizing the cross-entropy of held-out data, while for kneser-ney-fix these parameters are set
using the formula suggested by Kneser and Ney (1995), as described in Section 4.1. While theirperformances are sometimes very close, especially for large data sets, we see that kneser-ney consistently outperforms kneser-ney-fix. While not shown, these algorithms have similar behavior
on the other two corpora. (For a discussion of the anomalous points in Figures 19 and 21 for the
30,000-sentence training set, refer to Section 5.1.1.)
In Figures 20 and 21, we display the performance of kneser-ney-mod and kneser-ney-modfix for bigram and trigram models on the WSJ/NAB and Switchboard corpora over a range oftraining set sizes. As with kneser-ney and kneser-ney-fix, these algorithms di er in whether the
discounts are set using held-out data or using a formula based on training set counts. We see similar37diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

relative performance of algorithms on WSJ/NAB corpus, 2-gram
0.1

abs-disc-backoff

0.05
jelinek-mercer-baseline0
abs-disc-interp
-0.05
-0.1

kneser-ney-mod-backoff
-0.15
-0.2
100

kneser-ney-mod

1000
10000
training set size (sentences)

100000relative performance of algorithms on WSJ/NAB corpus, 3-gram
0.1
0.05
jelinek-mercer-baseline0

abs-disc-interp

-0.05
-0.1

abs-disc-backoff-0.15

kneser-ney-mod-backoff

-0.2
-0.25
-0.3
100

kneser-ney-mod
1000
10000
training set size (sentences)

100000relative performance of algorithms on Broadcast News corpus, 2-gram
0.05
jelinek-mercer-baseline0

abs-disc-interp

-0.05
-0.1

abs-disc-backoff
kneser-ney-mod-backoff-0.15
kneser-ney-mod
-0.2
100

1000
10000
training set size (sentences)

100000diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

Figure 15: Performance relative to baseline of backo and interpolated versions of absolute discounting and modi ed Kneser-Ney smoothing on WSJ/NAB corpus, bigram and trigram models
relative performance of algorithms on Broadcast News corpus, 3-gram
0.1
0.05
0
-0.05

abs-disc-interp
jelinek-mercer-baseline
kneser-ney-mod-backoff
abs-disc-backoff

-0.1
-0.15
-0.2

kneser-ney-mod

-0.25
100

1000
10000
training set size (sentences)

100000Figure 16: Performance relative to baseline of backo and interpolated versions of absolute discounting and modi ed Kneser-Ney smoothing on Broadcast News corpus, bigram and trigram
models38

jelinek-mercer-baseline

0

-0.05

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

relative performance of algorithms on WSJ/NAB corpus, 2-gram

kneser-ney

-0.1

-0.15

-0.2

100

kneser-ney-mod

1000

10000
100000
1e+06
training set size (sentences)

1e+07

relative performance of algorithms on WSJ/NAB corpus, 3-gramjelinek-mercer-baseline

0
-0.05

kneser-ney

-0.1
-0.15
-0.2
-0.25
kneser-ney-mod
100

1000

10000
100000
1e+06
training set size (sentences)

1e+07

Figure 17: Performance relative to baseline of kneser-ney and kneser-ney-mod algorithms on
WSJ/NAB corpus, bigram and trigram models
behavior as before: while their performance is often close, especially for large data sets, kneserney-mod consistently outperforms kneser-ney-mod-fix. While not shown, these algorithms have
similar performance on the other two corpora. While the -fix variations have the advantage of
not having any external parameters that need to be optimized, we see that we can generally do alittle better by optimizing parameters on held-out data. In addition, in situations where we haveheld-out data known to be similar to the test data, the variations with free parameters should dowell even if the training data does not exactly match the test data. This robustness is highlighted
for the 30,000-sentence training set from the Switchboard corpus, as discussed in Section 5.1.1.

5.1.5 Held-out and Deleted Estimation

In this section, we compare the held-out and deleted interpolation variations of Jelinek-Mercer
smoothing. In Figure 22, we display the performance of the jelinek-mercer and jelinek-mercer-delest
algorithms on the WSJ/NAB corpus for bigram and trigram models over a variety of training set
sizes. These two algorithms di er only in that jelinek-mercer uses the held-out data to optimize
the  parameters, while jelinek-mercer-delest optimizes the  parameters using deleted estimation (i.e., the leave-one-out technique). We see that jelinek-mercer performs signi cantly betterfor smaller training sets, but for large training sets jelinek-mercer-delest performs slightly
better.14
Smoothing can be viewed as modeling the di erence in nature between a training and test set.
Held-out data external to the training data will tend to be more di erent from the training data
than data that is deleted from the middle of the training data. As our evaluation test data is also
external to the training data (as is the case in applications), 's trained from held-out data may better characterize the evaluation test data. This may explain the superior performance of jelinekmercer on smaller data sets. We hypothesize that the reason why jelinek-mercer-delest does
well on larger data sets is that on larger training sets, data that is deleted from the middle of a
training set is suciently di erent from the remainder of the data that it is similar in nature to
14 These results di er slightly from those reported in previous work (Chen, 1996); in that work we reported that
held-out estimation is superior. However, in that work we did not use training sets as large as those in this work,so that we did not observe the cross-over point in performance.

39diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

relative performance of algorithms on WSJ/NAB corpus, 2-gramjelinek-mercer-baseline0kneser-ney-fix
-0.05

-0.1

-0.15

kneser-ney

-0.2
100

1000

10000
100000
1e+06
training set size (sentences)

1e+07

relative performance of algorithms on WSJ/NAB corpus, 3-gram
0.05
jelinek-mercer-baseline

0
-0.05
-0.1
-0.15

kneser-ney-fix-0.2
kneser-ney
-0.25
100

1000

10000
100000
1e+06
training set size (sentences)

1e+07

relative performance of algorithms on Switchboard corpus, 2-gram
0

-0.05

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

Figure 18: Performance relative to baseline of kneser-ney and kneser-ney-fix algorithms on
WSJ/NAB corpus, bigram and trigram models
jelinek-mercer-baseline

kneser-ney-fix-0.1

kneser-ney
-0.15

100

1000
10000
training set size (sentences)

100000relative performance of algorithms on Switchboard corpus, 3-gram
kneser-ney-fix

0.15
0.1
0.05
0

jelinek-mercer-baseline

-0.05
-0.1
kneser-ney

-0.15
-0.2
100

1000
10000
training set size (sentences)

100000Figure 19: Performance relative to baseline of kneser-ney and kneser-ney-fix algorithms on
Switchboard corpus, bigram and trigram models

40jelinek-mercer-baseline

0

-0.05

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

relative performance of algorithms on WSJ/NAB corpus, 2-gram

kneser-ney-mod-fix

-0.1

-0.15

-0.2
kneser-ney-mod
100

1000

10000
100000
1e+06
training set size (sentences)

1e+07

relative performance of algorithms on WSJ/NAB corpus, 3-gramjelinek-mercer-baseline

0
-0.05

kneser-ney-mod-fix

-0.1
-0.15
-0.2
-0.25

100

kneser-ney-mod
1000

10000
100000
1e+06
training set size (sentences)

1e+07

relative performance of algorithms on Switchboard corpus, 2-gramdiff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

Figure 20: Performance relative to baseline of kneser-ney-mod and kneser-ney-mod-fix algorithms on WSJ/NAB corpus, bigram and trigram models
jelinek-mercer-baseline

0

-0.05

-0.1
kneser-ney-mod-fix-0.15
kneser-ney-mod
-0.2
100

1000
10000
training set size (sentences)

100000relative performance of algorithms on Switchboard corpus, 3-gram
0

jelinek-mercer-baseline

-0.05

-0.1

kneser-ney-mod-fix

-0.15

-0.2
100

kneser-ney-mod
1000
10000
training set size (sentences)

100000Figure 21: Performance relative to baseline of kneser-ney-mod and kneser-ney-mod-fix algorithms on Switchboard corpus, bigram and trigram models

41

0.1

jelinek-mercer-delest

0.05

jelinek-mercer-baseline

0

-0.05
jelinek-mercer
-0.1
100

1000
10000
training set size (sentences)

relative performance of algorithms on WSJ/NAB corpus, 3-gramdiff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

relative performance of algorithms on WSJ/NAB corpus, 2-gram

1000000.04

jelinek-mercer-delest

0.02
jelinek-mercer-baseline

0
-0.02
-0.04
-0.06
jelinek-mercer

-0.08
-0.1
-0.12
100

1000
10000
training set size (sentences)

100000Figure 22: Performance relative to baseline of jelinek-mercer and jelinek-mercer-delest
algorithms on WSJ/NAB corpus, bigram and trigram models
held-out data. Thus, the preceding e ect is less pronounced, and perhaps because of the larger
amount of data used to optimize parameters, the performance of jelinek-mercer-delest becomessuperior. However, the implementation jelinek-mercer-delest does not completely characterize
the technique of deleted interpolation as we do not vary the size of the chunks that are deleted.

5.2 Count-by-Count Analysis

In order to paint a more detailed picture of the performance of various algorithms, instead of justlooking at the overall cross-entropy of a test set, we partition test sets according to how often eachn-gram in the test set occurred in the training data, and examine performance within each of thesepartitions. More speci cally, the cross-entropy of an n-gram model p of a test set T as expressedin equation (6) can be rewritten asXc (wi ) log p(w jwi 1 )H (T ) = 1
p

WT w i

T

i n+1

i n+1

i i n+1

2

where the sum ranges over all n-grams and cT (wii n+1 ) is the number of occurrences of the ngram wii n+1 in the test data. Instead of summing over all n-grams, consider summing only overn-grams with exactly r counts in the training data, for some r; i.e., consider the valueX
H (T ) = 1
c (wi ) log p(w jwi 1 )
(27)
p;r

WT w ii n+1 :c(wii n+1 )=r

T

i n+1

2

i i n+1

Then, we might compare the values of Hp;r (T ) between models p for each r to yield a more detailed
picture of performance.
However, there are two orthogonal components that determine the value Hp;r (T ), and it isinformative to separate them. First, there is the total probability mass Mp;r (T ) that a model puses to predict n-grams with exactly r counts given the histories in the test set, i.e., the valueXcT (wii n1 +1 )p(wi jwii n1 +1 )Mp;r (T ) =wii n+1 :c(wii n+1 )=r42

An interpretation of the value Mp;r (T ) is the expected count in the test set T of n-grams withr counts according to model p, given the histories in the test set. Ideally, the value of Mp;r (T )should match the actual number of n-grams in the test set T that have r counts in the training
data, cr (T ), whereX
cr (T ) =cT (wii n+1 )wii n+1 :c(wii n+1 )=r

The value Mp;r (T ) is proportional to the average probability a model p assigns to n-grams with rcounts; an algorithm with a larger Mp;r (T ) will tend to have a lower Hp;r (T ).
Now, consider a metric similar to Hp;r (T ) where we factor out the contribution of Mp;r (T ), sothat algorithms with a larger Mp;r (T ) will not tend to receive a better score. That is, consider
a metric where we scale probabilities so that all algorithms devote the same total probability to
n-grams with r counts for each r. In particular, we use the valueX
cr (T )i 1
 (T ) = 1i
Hp;rWT wi :c(wi )=r cT (wi n+1 ) log2 Mp;r (T ) p(wi jwi n+1 )
i n+1

i n+1

This is similar to de ning an (improper) distributionp (wi jwii n1 +1 ) = Mcr (T(T) ) p(wi jwii n1 +1 )p;rwhere we are assured Mp;r (T ) = cr (T ) as is ideal, and calculating the performance Hp ;r (T ) for (T ) assures that each model predicts each count r with thethis new model. As the measure Hp;rsame total mass, this value just measures how well a model distributes its probability mass amongn-grams with the same count.
To recap, we can use the measure Mp;r (T ) to determine how well a smoothed model p assigns
probabilities on average to n-grams with r counts in the training data; in particular, we want
Mp;r (T ) (or the ratio between expected and actual counts in the training data) to be near 1 for all
cr (T )
 (T ), which we refer to as normalized cross-entropy or normalized performance,r. The value Hp;rmeasures how well a smoothed model p distributes probabilities between n-grams with the same
count; as with cross-entropy, the lower the better.
We ran experiments with count-by-count analysis for two training set sizes, 30,000 sentences(about 750,000 words) and 3,700,000 sentences (about 75 million words), on the WSJ/NAB corpus.
We used a test set of about 10 million words; a larger test set was desirable because of the sparsenessof n-grams with exactly r counts for larger r.

5.2.1 Expected vs. Actual Counts, Overall(T )In Figure 23, we display the ratio of expected to actual counts Mcp;rr (T ) for various algorithms on
the larger training set for bigram and trigram models for low counts r  5. In Figure 24, we havethe analogous graphs for higher counts 5  r < 40.15 For low counts, we see that the algorithms
katz and kneser-ney-mod come closest to the ideal value of 1. The values farthest from the ideal
are attained by the methods jelinek-mercer-baseline, jelinek-mercer, and witten-bellbackoff. These algorithms assign signi cantly too much probability on average to n-grams withlow counts. For high counts, katz is nearest to the ideal.
i 1
15 For the zero-count case, we exclude those n-grams wi
i n+1 for which the corresponding history wi n+1 has noPi1
counts, i.e., for which wi c(wi n+1 wi ) = 0.

43

ratio of expected to actual counts, 2-gram, 75M words training

1.8
1.6
1.4

ideal
jelinek-mercer-baseline
jelinek-mercer
witten-bell-backoff
katzkneser-ney-mod
kneser-ney
abs-disc-interp

2.2

expected count / actual count2

expected count / actual countratio of expected to actual counts, 3-gram, 75M words training
2.4

ideal
jelinek-mercer-baseline
jelinek-mercer
witten-bell-backoff
katzkneser-ney-mod
kneser-ney
abs-disc-interp

1.2
1
0.8

2
1.8
1.6
1.4
1.2
1
0.8

0.6

0.6
0

1

2

3

4

5

0

1

2

count

3

4

5

count

Figure 23: Ratio of expected number to actual number in test set of n-grams with a given countin training data for various smoothing algorithms, low counts, WSJ/NAB corpus, bigram andtrigram models
ratio of expected to actual counts, 2-gram, 75M words training

ratio of expected to actual counts, 3-gram, 75M words training

1.5

1.5
ideal
abs-disc-interp
kneser-ney
kneser-ney-mod
katz
jelinek-mercer-baseline
jelinek-mercer
witten-bell-backoff

1.3
1.2

ideal
abs-disc-interp
kneser-ney
kneser-ney-mod
katz
jelinek-mercer-baseline
jelinek-mercer
witten-bell-backoff

1.4

expected count / actual countexpected count / actual count

1.4

1.1
1
0.9

1.3
1.2
1.1
1
0.9

0.8

0.8
5

10

15

20
25
count

30

35

5

10

15

20
25
count

30

35

Figure 24: Ratio of expected number to actual number in test set of n-grams with a given countin training data for various smoothing algorithms, high counts, WSJ/NAB corpus, bigram andtrigram models

44

1M words training

200M words training

2

2

average correct discountaverage correct discounttrigram
1.5
bigram

1

0.5

0

1.5

trigram1bigram
0.5

0
1

3

5

7
original count

9

11

13

1

3

5

7
original count

9

11

13

Figure 25: Correct average discount for n-grams with a given count in training data on two training
set sizes, WSJ/NAB corpus, bigram and trigram models
To explain these behaviors, we calculate the ideal average discount for each count. Thatis, consider all n-grams wii n+1 with count r. Let us assume that we perform smoothing by
pretending that all such n-grams actually receive r counts; i.e., instead of the maximum-likelihood
distributionpML(wi jwii n1 +1 ) = i r 1c(wi n+1 )we takep0 (wi jwii n1 +1 ) = ir 1c(wi n+1 )Then, we can calculate the value of r such that the ideal probability mass Mp0 ;r (T ) = cr (T ) is
achieved. We take r r for the ideal r to be the ideal average discount for count r. This is an
estimate of the correct number of counts on average to take away from all n-grams with r counts
in the training data. In Figure 25, we graph the empirical estimate of this value for r  13 forbigram and trigram models for a one million and 200 million word training set. (For values abover = 13, the graph becomes very noisy due to data sparsity.) We can see that for very small r thecorrect discount rises quickly, and then levels o .
In other words, it seems that a scheme that discounts di erent r uniformly is more appropriate
than a scheme that assigns discounts that are proportional to r. Algorithms that fall under theformer category include abs-disc-interpand kneser-ney; these algorithms use a xed discountDn over all counts. Algorithms that fall in the latter category include all three algorithms that
fared poorly in Figures 23 and 24: jelinek-mercer-baseline, jelinek-mercer, and wittenbell-backoff. These algorithms are all of the form given in equation (12)pinterp(wi jwii n1 +1 ) = wii n1 +1 pML (wi jwii n1 +1 ) + (1 wii n1 +1 ) pinterp(wi jwii n1 +2 )where the discount of an n-gram with count r is approximately r r. Because discounts arelinear in r when ideally they should be roughly constant, discounts for these algorithms were too
low for low counts and too high for high counts.
Katz smoothing chooses discounts according to the Good-Turing discount, which theoreticallyshould estimate the correct average discount well, and we nd this to be the case empirically.
45

While Katz assigns the correct total mass to n-grams with a particular count, it does not performparticularly well because it does not distribute probabilities well between n-grams with the same
count, as we shall see when we examine its normalized cross-entropy.
The algorithm kneser-ney-mod uses a uniform discount Dn;3+ for all counts three and above,
but separate discounts Dn;1 and Dn;2 for one- and two-counts. This modi cation of Kneser-Ney
smoothing was motivated by the observation in Figure 25 that smaller counts have a signi cantly
di erent ideal average discount than larger counts. Indeed, in Figure 23 we see that kneser-neymod is much closer to the ideal than kneser-ney for low counts. (The performance gain in using
separate discounts for counts larger than two is marginal.)

5.2.2 Normalized Performance, Overall (T ) of various algorithms relative to the
In Figure 26, we display the normalized cross-entropy Hp;rnormalized cross-entropy of the baseline algorithm on the 75 million word training set for bigram
and trigram models for low counts r  5. In Figure 27, we have the analogous graphs for higher
counts 5  r < 40. For the points on the graph with a count of 0, we excludeP
those n-grams wii n+1
i1
for which the corresponding history wi n+1 has no counts, i.e., for which wi c(wii n1 +1 wi ) = 0.
The associated values for these cases are displayed under a count value of -1.
We see that kneser-ney and kneser-ney-mod signi cantly outperform all other algorithms on
low counts, especially for the point with a count value of zero. We attribute this to the modi ed
backo distribution that is used in Kneser-Ney smoothing as described in Section 2.7. As theratio of expected to actual counts for these algorithms is not signi cantly superior to those for allother algorithms, and as their normalized performance on high counts is good but not remarkable,
we conclude that their excellent normalized performance on low counts is the reason for theirconsistently superior overall performance.
The algorithms with the worst normalized performance on low (nonzero) counts are katz andwitten-bell-backoff; these are also the only two algorithms shown that use backo insteadof interpolation. Thus, it seems that for low counts lower-order distributions provide valuable
information about the correct amount to discount, and thus interpolation is superior for thesesituations. Backo models do not use lower-order distributions to help estimate the probability ofn-grams with low (nonzero) counts.
For large counts, the two worst performing algorithms are jelinek-mercer and jelinekmercer-baseline. We hypothesize that this is due to a combination of two factors. First, bothalgorithms use linear discounting, which as mentioned in Section 5.2.1 leads to large discounts
for large counts. Second, these models are interpolated as opposed to backo models, so thatthese discounts vary according to lower-order models. Because of these two factors, discounts for
n-grams with large counts can vary widely from n-gram to n-gram. Given that smoothing methods
that assign the same probability to n-grams with a given count across di erent distributions (suchas Katz) perform well on large counts, we hypothesize that the ideal discount for n-grams witha given high count r should not vary much. This mismatch in the variation of discounts could
explain the poor performance of jelinek-mercer and jelinek-mercer-baseline in this domain.
All of the other algorithms are very near to each other in terms of normalized performance on large
counts; we guess that it does not matter much how large counts are smoothed as long as they are
not modi ed too much.

46

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

normalized performance for each count, 2-gram, 75M words training

0
-0.2
katz
witten-bell-backoff
abs-disc-interp
jelinek-mercer
kneser-ney
kneser-ney-mod

-0.4
-0.6
-0.8

-1

0

1

2
count

3

4

5

normalized performance for each count, 3-gram, 75M words training
0.3
0.2
0.1
0
-0.1
-0.2
katz
witten-bell-backoff
abs-disc-interp
jelinek-mercer
kneser-ney
kneser-ney-mod

-0.3
-0.4
-0.5
-1

0

1

2
count

3

4

5

normalized performance for each count, 2-gram, 75M words training
0.06
jelinek-mercer
abs-disc-interp
0.04
witten-bell-backoff
kneser-ney
0.02
kneser-ney-modkatz
0

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

Figure 26: Normalized cross-entropy for n-grams with a given count in training data for various
smoothing algorithms, low counts, WSJ/NAB corpus, bigram and trigram models

-0.02
-0.04
-0.06
-0.08
-0.1
5

10

15

20
25
count

30

35

normalized performance for each count, 3-gram, 75M words training
0.06
jelinek-mercer
abs-disc-interp
0.04
witten-bell-backoff
kneser-ney
0.02
kneser-ney-mod
katz
0
-0.02
-0.04
-0.06
-0.08
-0.1
5

10

15

20
25
count

30

35

Figure 27: Normalized cross-entropy for n-grams with a given count in training data for various
smoothing algorithms, high counts, WSJ/NAB corpus, bigram and trigram models

47bigram model

trigram model
1

r<=infinity

0.8

r<=2
r<=1

0.6

cumulative fraction of cross-entropy

cumulative fraction of cross-entropy

1

r<=10

r=0

0.4

0.2

0
100

1000

10000
100000
1e+06
training set size (sentences)

0.8
r<=2

0.6

r<=10

r<=1
r=0

0.4

0.2

0
100

1e+07

r<=infinity

1000

10000
100000
1e+06
training set size (sentences)

1e+07

Figure 28: Cumulative fraction of cross-entropy on test set devoted to n-grams with r or fewer
counts in training data for various r on WSJ/NAB corpus, jelinek-mercer-baseline smoothing,bigram and trigram models

5.2.3 Performance Variation Over Training Set Size

Given the preceding analysis, it is relevant to note what fraction of the total entropy of the test
data is associated with n-grams of di erent counts, to determine how the performance for eachcount a ects overall performance. In Figure 28, we display the cumulative values of HHp;rp ((TT)) (seeequation (27)) for di erent counts r for the baseline algorithm over a range of training set sizes forbigram and trigram models on the WSJ/NAB corpus. A line
labeled r  k graphs the fraction ofPk
Hp;r (T )the entropy devoted to n-grams with up to k counts, i.e., r=0
Hp (T ) . Actually, this is not quite
accurate, as we exclude from this value the contribution from all n-grams wii n+1 for which thecorresponding history wii n1 +1 has no counts. The contribution from these n-grams represent thearea above the r  1 line.
As would be expected, the proportion of the entropy devoted to n-grams with high counts
grows as the size of the training set grows. More surprising is the fraction of the entropy devoted
to low counts in trigram models even for very large training sets; for a training set of 10 million
sentences about 40% of the entropy comes from trigrams with zero counts in the training data.
This explains the large impact that performance on low counts has on overall performance, andwhy modi ed Kneser-Ney smoothing has the best overall performance even though it excels mostly
on low counts only.
In combination with the previous analysis, this data also explains some of the variation in therelative performance of di erent algorithms over di erent training set sizes and between bigram
and trigram models. In particular, algorithms that perform well on low counts will perform welloverall when low counts form a larger fraction of the total entropy (i.e., small data sets), andconversely, algorithms that perform well on high counts will perform better on large data sets.
For example, the observation that jelinek-mercer outperforms katz on small data sets whilekatz is superior on large data sets is explained by the fact that katz is superior on high counts
while jelinek-mercer is superior on low counts. Similarly, since bigram models contain morehigh counts than trigram models on the same size data, katz performs better on bigram models
than on trigram models.
48

5.2.4 Backo vs. Interpolation

In this section, we examine the count-by-count performance of the backo and interpolated versionsof several smoothing algorithms, namely the algorithms: witten-bell-interp and witten-bellbackoff, abs-disc-interpand abs-disc-backoff, and kneser-ney-mod and kneser-ney-modbackoff.
In Figures 29 and 30, we display the normalized performance of the backo and interpolated
versions of Witten-Bell and modi ed Kneser-Ney smoothing over a range of counts for both bigram
and trigram models. We can see that the interpolated algorithms signi cantly outperform thebacko algorithms on low (positive) counts. Though not shown, this holds for absolute discounting
as well. As discussed in Section 5.2.2, it seems that for low counts lower-order distributions provide
valuable information about the correct amount to discount, and thus interpolation is superior forthese situations.
In Figures 31 and 32, we display the ratio of expected to actual counts of the backo andinterpolated versions of Witten-Bell and modi ed Kneser-Ney smoothing over a range of counts
for both bigram and trigram models. For modi ed Kneser-Ney smoothing, we see that the backo
version is generally closer to the ideal according to this criterion. Though not shown, we see
similar behavior for absolute discounting. For Witten-Bell smoothing, we see that the backo
version is closer to the ideal for small counts, but not quite as close for large counts. However, theinterpolated version is signi cantly worse for the count of zero, being a factor of 1.5{2 away fromthe ideal. We hypothesize that the better performance of the backo model on low counts on thiscriterion is the reason for its better overall performance.
Thus, we see that for these models the interpolated versions generally have better normalized
cross-entropies, while the backo versions have more ideal expected-to-actual count ratios. We
hypothesize that the relative strength of these two in uences determine the relative performanceof the backo and interpolated versions of an algorithm. Since the relative strengths of thesefactors vary, whether the backo or interpolated version of an algorithm is superior depends on
the algorithm, as we have seen earlier.

5.3 Auxiliary Experiments

5.3.1 Higher Order n-Gram Models

Due to the increasing speed and memory of computers, there has been some use of higher-ordern-gram models such as 4-gram and 5-gram models in speech recognition in recent years (Seymore
et al., 1997; Weng, Stolcke, and Sankar, 1997). In this section, we examine how various smoothingalgorithms perform for these larger models.
In Figure 33, we display the performance of 2-gram through 5-gram models relative to a trigram model (all with jelinek-mercer-baseline smoothing) on various training set sizes on the
WSJ/NAB corpus. As would be expected, the larger the training set, the larger the gain in using
a higher-order model. For very large data sets, the gain in using a 4-gram or 5-gram model overa trigram model can become quite signi cant, over 0.2 bits/word. Note that all of these models
were built with no count cuto s; Chen (1996) gives a description of our implementation.
In Figure 34, we display the relative performance of various smoothing algorithms relative
to the baseline method for 4-gram and 5-gram models over a range of training set sizes on the
WSJ/NAB corpus. Again, we see kneser-ney and kneser-ney-mod consistently outperforming
the other algorithms. In addition, we see that algorithms that do not perform well on small data
sets for bigram and trigram models perform somewhat worse on these higher-order models, as theuse of a larger model exacerbates the sparse data problem. The methods katz, abs-disc-interp,
49

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

normalized performance for each count, 2-gram, 75M words training
witten-bell-backoff
jelinek-mercer-baseline

0

-0.1

-0.2

-0.3
witten-bell-interp
-0.4
0

5

10

15

20
count

25

30

35

normalized performance for each count, 3-gram, 75M words training
0.2

witten-bell-backoff

0.15
0.1
0.05
jelinek-mercer-baseline

0
-0.05

witten-bell-interp
-0.1
-0.15
-0.2
-0.25
0

5

10

15

20
count

25

30

35

n

normalized performance for each count, 2-gram, 750k words training

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

Figure 29: Normalized cross-entropy for -grams with a given count in training data for wittenbell-backoff and witten-bell-interp, WSJ/NAB corpus, bigram and trigram models
kneser-ney-mod-backoff
0.1
jelinek-mercer-baseline0kneser-ney-mod

-0.1
-0.2
-0.3
-0.4
0

5

10

15

20
count

25

30

35

normalized performance for each count, 3-gram, 750k words training
0.4
kneser-ney-mod-backoff
0.3
0.2
0.1
jelinek-mercer-baseline

0
-0.1
-0.2
-0.3

kneser-ney-mod
0

5

10

15

20
count

25

30

35

Figure 30: Normalized cross-entropy for n-grams with a given count in training data forkneser-ney-mod and kneser-ney-mod-backoff, WSJ/NAB corpus, bigram and trigram models

50

ratio of expected to actual counts, 3-gram, 75M words training

witten-bell-interp

witten-bell-interp

expected count / actual count

1.8

expected count / actual countratio of expected to actual counts, 2-gram, 75M words training

1.6
1.4
1.2
ideal

1
witten-bell-backoff
0.8

2

1.5

ideal

1
witten-bell-backoff
0.5

0.6
0

5

10

15

20
count

25

30

35

0

5

10

15

20
count

25

30

35

Figure 31: Ratio of expected number to actual number in test set of n-grams with a given countin training data for witten-bell-backoff and witten-bell-interp, WSJ/NAB corpus, bigram
and trigram models
ratio of expected to actual counts, 2-gram, 750k words training

ratio of expected to actual counts, 3-gram, 750k words training
kneser-ney-mod

kneser-ney-mod

1.15

expected count / actual countexpected count / actual count

1.1

1.05

1

ideal
kneser-ney-mod-backoff

0.95

1.1
1.05
1

ideal

0.95
kneser-ney-mod-backoff
0.9

0.9

0.85
0

5

10

15

20
count

25

30

35

0

5

10

15

20
count

25

30

35

Figure 32: Ratio of expected number to actual number in test set of n-grams with a given countin training data for kneser-ney-mod and kneser-ney-mod-backoff, WSJ/NAB corpus, bigram
and trigram models

51difference in test cross-entropy from trigram (bits/token)

relative performance of n-gram orders on WSJ/NAB corpus
0.8
2-gram0.6
0.4
0.2
3-gram04-gram-0.2

5-gram
-0.4
100

1000

10000
100000training set size (sentences)

1e+06

relative performance of algorithms on WSJ/NAB corpus, 4-gram
0.1
0.05

abs-disc-interp

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

Figure 33: Performance relative to trigram model of n-gram models of varying order on WSJ/NAB
corpus, jelinek-mercer-baseline smoothing

witten-bell-backoff

katz

0

baseline-0.05

jelinek-mercer

-0.1
-0.15

kneser-ney
kneser-ney-mod

-0.2
-0.25
-0.3
100

1000

10000
100000training set size (sentences)

1e+06

0.1
0.05

relative performance of algorithms on WSJ/NAB corpus, 5-gramabs-disc-interp
w-b-b
katz

0

jelinek-mercer-baseline-0.05
jelinek-mercer-0.1
kneser-ney-0.15

kneser-ney-mod

-0.2
-0.25
-0.3
100

1000

10000
100000training set size (sentences)

1e+06

Figure 34: Performance relative to baseline of various algorithms on WSJ/NAB corpus, 4-gram
and 5-gram models

52and witten-bell-backoff perform about as well or worse than the baseline algorithm except for
the largest data sets. On the other hand, jelinek-mercer consistently outperforms the baseline
algorithm.

5.3.2 Count Cuto s

For large data sets, count cuto s are often used to restrict the size of the n-gram model constructed.
With count cuto s, all n-grams of a certain length with fewer than a given number of occurrencesin the training data are ignored in some fashion. How counts are \ignored" is algorithm-speci c,and has not generally been speci ed in the original descriptions of previous smoothing algorithms.
In these experiments, we implemented what we felt was the most \natural" way to add cuto s tovarious algorithms. The general strategy we took was: for n-grams with counts below the cuto s,
we pretended they occurred zero times and assigned probabilities through backo /interpolation;
for n-grams with counts above the cuto s, we assigned similar probabilities as in the non-cuto
case; and we adjusted the backo /interpolation scaling factors so that distributions were correctly
normalized.
For instance, for Katz smoothing (Section 2.4) we use the identical dr as in the non-cuto case,but instead of equation (13) we use the following equation
dr r
if r > rcut
(wi 1 ) pML(wi ) if r  rcut
where rcut is the corresponding cuto , and where (wi 1 ) is still chosen so that the total number
ckatz (wii 1 ) =of counts in the distribution is unchanged. Later in this section, we brie y describe our countcuto implementations for various algorithms.
To introduce the terminology we use to describe cuto models, we use an example: 0-0-1 cuto s
for a trigram model signals that all unigrams with 0 or fewer counts are ignored, all bigrams with
0 or fewer counts are ignored, and all trigrams with 1 or fewer counts are ignored. Models with no
cuto s can be said to have 0-0-0 cuto s. Using cuto s of one or two for bigrams and trigrams cangreatly decrease the size of a model, while yielding only a small degradation in performance.
In Figure 35, we display the performance of bigram and trigram models with di erent cuto s
relative to the corresponding model with no cuto s for jelinek-mercer-baseline smoothingon various training set sizes on the WSJ/NAB corpus. For bigram models, we see that models
with higher cuto s tend to perform more poorly as would be expected, though for very large
training sets 0-1 cuto s are comparable with no cuto s. However, for trigram models we see thatmodels with 0-0-1 cuto s actually outperform models with no cuto s over most of the training set
sizes. In other words, it seems that the algorithm jelinek-mercer-baseline smooths trigramswith one count so poorly that using these counts actually hurts performance. To show that thisbehavior does not hold for all smoothing algorithms, in Figure 36 we display the graph analogous
to the graph on the right of Figure 35 except using kneser-ney-mod instead of jelinek-mercerbaseline smoothing. For kneser-ney-mod, we see that models with cuto s indeed perform morepoorly than models without cuto s. The decrease in performance is moderate for these cutovalues, though, especially for larger data sets (about 0.05 bits/word).
In Figures 37 and 38, we display the performance of various smoothing algorithms for bigram
and trigram models, respectively, for di erent cuto s over a range of training set sizes on the
WSJ/NAB corpus. Overall, we see that the ordering of algorithms by performance is largely
unchanged from the non-cuto case; kneser-ney and kneser-ney-mod still yield the best performance. The most signi cant di erence is that our implementation abs-disc-interpperforms
53difference in test cross-entropy from no cutoffs (bits/token)

difference in test cross-entropy from no cutoffs (bits/token)

relative performance of cutoffs on WSJ/NAB corpus, bigram
0-2 cutoffs

0.12
0.1
0.08
0.06
0.04

0-1 cutoffs

0.02
0
100

no cutoffs
1000

10000
100000training set size (sentences)

1e+06

relative performance of cutoffs on WSJ/NAB corpus, trigram
0.1

0-1-1 cutoffs

0.05
0-0-2 cutoffs
no cutoffs

0

-0.05
0-0-1 cutoffs

-0.1
100

1000

10000
100000training set size (sentences)

1e+06

difference in test cross-entropy from no cutoffs (bits/token)

Figure 35: Performance relative to model with no count cuto s of models with cuto s on WSJ/NAB
corpus, jelinek-mercer-baseline smoothing, bigram and trigram models
relative performance of cutoffs on WSJ/NAB corpus, trigram
0.2
0-1-1 cutoffs
0.15

0.1
0-0-2 cutoffs
0.05

0-0-1 cutoffs

0100

no cutoffs
1000

10000
100000training set size (sentences)

1e+06

Figure 36: Performance relative to model with no count cuto s of models with cuto s on WSJ/NAB
corpus, kneser-ney-mod smoothing, trigram model54

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

rel. perf. of algs. on WSJ/NAB corpus, 2-gram, 0-1 cutoffs
0.1
abs-disc-interp
0.05
witten-bell-backoff
0jelinek-mercer
katz

-0.05
kneser-ney-mod

-0.1
100

1000

kneser-ney

10000
100000training set size (sentences)

1e+06

rel. perf. of algs. on WSJ/NAB corpus, 2-gram, 0-2 cutoffs
0.1
0.08
abs-disc-interp

0.06
0.04

witten-bell-backoff

0.02

jelinek-mercer-baseline0jelinek-mercer

-0.02

katz

-0.04
-0.06

kneser-ney-mod

kneser-ney

-0.08
100

1000

10000
100000training set size (sentences)

1e+06

rel. perf. of algs. on WSJ/NAB corpus, 3-gram, 0-0-1 cutoffs
0.1

diff in test cross-entropy from baseline (bits/token)

diff in test cross-entropy from baseline (bits/token)

Figure 37: Performance relative to baseline of various algorithms on WSJ/NAB corpus, bigram
model with 0-1 and 0-2 cuto s
witten-bell-backoff

0.05

abs-disc-interp

0jelinek-mercer-baseline
katz

-0.05
jelinek-mercer
kneser-ney-0.1
kneser-ney-mod
-0.15
-0.2
100

1000

10000
100000training set size (sentences)

1e+06

0.1

rel. perf. of algs. on WSJ/NAB corpus, 3-gram, 0-1-1 cutoffs
abs-disc-interp
witten-bell-backoff

0.05
jelinek-mercer-baseline

0
j-m

katz
-0.05
kneser-ney-mod

kneser-ney

-0.1

100

1000

10000
100000training set size (sentences)

1e+06

Figure 38: Performance relative to baseline of various algorithms on WSJ/NAB corpus, trigram
model with 0-0-1 and 0-1-1 cuto s55

more poorly relative to the other algorithms; it generally performs worse than the baseline algorithm, unlike in the non-cuto case. In addition, the magnitudes of the di erences in performanceseem to be less when cuto s are used. For example, for trigram models with cuto s, kneser-neymod performs up to 0.15 bits/word better than jelinek-mercer-baseline; for models with no
cuto s, this value is around 0.25 bits/word.

Cuto Implementations In this section, we brie y describe our implementations for countcuto s for various algorithms. As mentioned earlier, the general strategy we took was: for n-gramswith counts below the cuto s, we pretended they occurred zero times and assigned probabilities
through backo /interpolation; for n-grams with counts above the cuto s, we assigned similar
probabilities as in the non-cuto case; and we adjusted the backo /interpolation scaling factors sothat distributions were correctly normalized. For the implementation of cuto s for Katz smoothing,refer to the beginning of Section 5.3.2.
For jelinek-mercer and jelinek-mercer-baseline, we use an equation analogous to equation (12) from Section 2.3:
pinterp(wi jwii n1 +1 ) = 0wii n1 +1 pcut(wi jwii n1 +1 ) + (1 0wii n1 +1 ) pinterp(wi jwii n1 +2 )
where

(28)

i

and wherepcut(wi jwii n1 +1 ) = Pccutc (w(i wni+1 ) )wi cut i n+1

ccut(wii n+1 ) =c(wii n+1 ) if c(wii n+1 ) > cn

0otherwise
where cn is the count cuto for that n-gram level. For 0wi 1 , we take
i n+1

P

c (wii n+1 )0wii n1 +1 = Pwi cut
c(wi ) wii n1 +1
i n+1

wi

Then, the left term on the right-hand side of equation (28) is equivalent to the corresponding termin equation (12); i.e., n-grams with counts above the cuto are assigned similar probabilities in
the cuto and non-cuto cases.
For Witten-Bell smoothing, instead of equation (17) in Section 2.5 we takec (wi ) + N 0 (wi 1 )p (wi jwii n1 +2 )pWB (wi jwii n1 +1 ) = cut i Pn+1 i 1+ i n+1 WB
i 1
wi c(wi n+1 ) + N1+ (wi n+1 )
0 (wi 1 ) is chosen so that probabilities sum towhere ccut(wii n+1 ) is de ned as before and N1+i n+11; i.e., we take0 (wi 1 ) = N1+ (wi 1 ) +
N1+
i n+1
i n+1

X

wi

c(wii n+1 )X

wiccut(wii n+1 )For absolute discounting, we use an equation analogous to equation (18) in Section 2.6
ipabs (wi jwii n1 +1 ) = maxfcPcut(wc(i wni+1 ) ) D; 0g + (1 wii n1 +1 ) pabs (wi jwii n1 +2 )
wi

i n+1

56

9.5

52

abs-disc-interp
katz
kneser-ney-fix
kneser-ney-mod

abs-disc-interp
katz
kneser-ney-fix
kneser-ney-mod

50

word-error rate on test set

cross-entropy of test data (bits/token)

10

9
8.5
8

48
46
44
42
40
38

7.5
36
7
1000

34
10000
100000
1e+06
training set size (sentences)

1000

10000
100000
1e+06
training set size (sentences)

Figure 39: On left, cross-entropy of various algorithms on Broadcast News speech recognition test
set over various training set sizes, trigram model; on right, speech recognition word-error rate forsame models on same test set
To have this distribution sum to 1, instead of equation (19) we takeP

D N1+ (wii n1 +1 ) + Pwi c(wii n+1 )1 wii n1 +1 =iwi c(wi n+1 )Piwi ccut (wi n+1 )For Kneser-Ney smoothing, we make the same adjustments as in absolute discounting.

5.3.3 Cross-Entropy and Speech Recognition

In this section, we brie y examine how the performance of a language model measured in termsof cross-entropy correlates with speech recognition performance using the language model. Speech
recognition is perhaps the most prevalent application of language models, and we perform thisstudy to give an example of how cross-entropy correlates with an application-speci c measure of
performance. Speech recognition performance is generally measured in terms of word-error rate,
which is the number of word errors made divided by the number of words in the correct transcript.
It has been shown previously that there is some linear correlation between the word-error rate
produced using a language model and the cross-entropy of the model on the corresponding text
(Chen, Beeferman, and Rosenfeld, 1998). However, the strength of the correlation depends on thenature of the models being compared.
For these experiments, we used Broadcast News speech data (DARPA, 1998). We generated
narrow-beam lattices with the Sphinx-III speech recognition system (Placeway et al., 1997) using
a Katz-smoothed trigram model trained on 130 million words of Broadcast News text; trigrams
occurring only once in the training data were excluded from the model. We calculated word-error
rates for the language models in this experiment by rescoring these lattices with the given language
model.
We constructed trigram language models for each of four smoothing algorithms for ve di erent
training set sizes (ranging from 1,000 to 8,300,000 sentences). Listed from best to worst in termsof cross-entropy, these algorithms are kneser-ney-mod, kneser-ney-fix, katz, and abs-discinterp. All models were built with no count cuto s except for the largest training set, for which57

52
abs-disc-interp
katz
kneser-ney-fix
kneser-ney-mod

word-error rate on test set

50
48
46
44
42
40
38
36
34
7

7.5

8

8.5
9
9.5
cross-entropy of test set

10

10.5

Figure 40: Relation between perplexity and speech recognition word-error rate on test set for 20
language models
trigrams occurring only once in the training data were excluded. The cross-entropy on the test
data of these 20 models are displayed on the left in Figure 39 by training set size.
Then, we calculated word-error rates for each of these 20 models on the test data using theprocedure described earlier. On the right in Figure 39, we plot the word-error rates of these 20
models by training set size. In Figure 40, we plot the cross-entropy vs. the word-error rate for eachof the 20 models. We can see that the linear correlation between cross-entropy and word-error
rate is very strong for this set of models. Thus, it seems that smoothing algorithms with lower
cross-entropies will generally lead to lower word-error rates when plugged into speech recognition
systems. For our particular data set, we see a reduction of about 5.4% absolute in word-error rate
for every bit of reduction in cross-entropy. As seen in Section 5.1, the di erence in cross-entropy
between the best smoothing algorithm and a mediocre smoothing algorithm can be 0.2 bits or
more, corresponding to about a 1% absolute di erence in word-error rate. Hence, the choice ofsmoothing algorithm can make a signi cant di erence in speech recognition performance.

6 Discussion
Smoothing is a fundamental technique for statistical modeling, important not only for language
modeling but for many other applications as well, e.g., prepositional phrase attachment (Collins
and Brooks, 1995), part-of-speech tagging (Church, 1988), and stochastic parsing (Magerman,
1994; Goodman, 1997). Whenever data sparsity is an issue, smoothing can help performance, anddata sparsity is almost always an issue in statistical modeling. In the extreme case where there isso much training data that all parameters can be accurately trained without smoothing, one canalmost always expand the model, such as by moving to a higher-order n-gram model, to achieve
improved performance. With more parameters data sparsity becomes an issue again, but withproper smoothing the models are usually more accurate than the original models. Thus, no matter
how much data one has, smoothing can almost always help performance, and for a relatively smalle ort.
In this work, we have measured the performance of smoothing algorithms primarily throughthe cross-entropy of test data, and we have also performed experiments measuring the worderror rate of speech recognition. Cross-entropy does not always correlate well with word-error
58rate, especially when the models compared are created using very di erent techniques (Chen,
Beeferman, and Rosenfeld, 1998). However, in our experiments we found that when the only
di erence between models is smoothing, the correlation between the two measures is quite strong.
It is certainly possible that in other domains, improved cross-entropy from better smoothing will
not correlate with improved application performance, but we expect that in most cases it will. For
speech recognition, better smoothing algorithms may lead to up to a 1% absolute improvement inword-error rate.
To our knowledge, this is the rst empirical comparison of smoothing techniques in language
modeling of such scope: no other study has systematically examined multiple training data sizes,
di erent corpora, or has performed automatic parameter optimization. We show that in order
to completely characterize the relative performance of two techniques, it is necessary to consider
multiple training set sizes and to try both bigram and trigram models. We show that sub-optimal
parameter selection can signi cantly a ect relative performance. We have also developed a novelsmoothing algorithm that outperforms all previous techniques, by applying insights gleaned fromusing the tools that we have created for the detailed analysis of smoothing algorithms.
Multiple runs should be performed whenever possible to discover whether any calculated di erences are statistically signi cant; it is unclear whether many of the previously reported results inthe literature are conclusive given that they are based on single runs and given the variances foundin this work. For example, we estimated that the standard deviation of the performance of Katz
smoothing relative to the baseline method for a single run is about 0:015 bits, which translates toabout a 1% di erence in perplexity. This standard deviation is comparable to previously reported
di erences in performance. For instance, in the Nadas and Katz papers, di erences in perplexity
between algorithms of about 1% are reported for a single test set of 100 sentences. MacKay andPeto present perplexity di erences between algorithms of signi cantly less than 1%.
We point out that because of the variation in the performance of di erent smoothing methods and the variation in the performance of di erent implementations of the same smoothing
method (e.g., from parameter setting), it is vital to specify the exact smoothing technique andimplementation of that technique used when referencing the performance of an n-gram model.
For example, the Katz and Nadas papers describe comparisons of their algorithms with \JelinekMercer" smoothing, but they do not specify the bucketing scheme used or the granularity used indeleted interpolation. Without this information, it is impossible to determine the import of theircomparisons. More generally, there has been much work comparing the performance of various
models with that of n-gram models where the type of smoothing used is not speci ed. Again,
without this information we cannot tell if the comparisons are signi cant.
Of the techniques studied, we have found that Kneser-Ney smoothing and variations consistently outperform all other algorithms. In particular, our novel algorithm kneser-ney-mod consistently had the best performance. This algorithm di ers in several ways from Kneser and Ney's
original algorithm: interpolation is used instead of backo , we use a separate discount for oneand two-counts instead of a single discount for all counts, and we estimate discounts on held-out
data instead of using a formula based on training data counts. Our experimental results show that
all three of these choices improve performance. Performing just slightly worse is the algorithm
kneser-ney-mod-fix; this algorithm di ers from kneser-ney-mod in that discounts are set using
a formula based on training data counts. This algorithm has the practical advantage that noexternal parameters need to be optimized on held-out data.
We provide techniques for analyzing the count-by-count performance of di erent smoothing
techniques. This detailed analysis helps explain the relative performance of various algorithms,
and can help predict how di erent algorithms will perform in novel situations. These analysis tools
helped us design our modi cations to Kneser-Ney smoothing.
59

From our experiments and analysis, we found several factors that had a consistent e ect on theperformance of smoothing algorithms.
 The factor with the largest in uence is the use of a modi ed backo distribution as in KneserNey smoothing. This seemed to be the primary reason that the variations of Kneser-Ney
smoothing performed so well relative to the remaining algorithms.
 Absolute discounting is superior to linear discounting. As was shown earlier, the ideal average
discount for counts rises quickly for very low counts but is basically at for larger counts.
However, the Good-Turing estimate can be used to predict this average discount even better
than absolute discounting, as was demonstrated by Katz smoothing.
 In terms of normalized performance, interpolated models are signi cantly superior to backo models for low (nonzero) counts. This is because lower-order models provide valuable
information in determining the correct discount for n-grams with low counts.
 Adding free parameters to an algorithm and optimizing these parameters on held-out data
can improve the performance of an algorithm, e.g., kneser-ney-mod vs. kneser-ney-modfix.
Our algorithm kneser-ney-mod gets its superior performance from a combination of all of thesefactors.
While we have systematically explored smoothing for n-gram language models, there remain
many directions that need to be explored. Almost any statistical model, not just n-gram models,can and should be smoothed, and further work will be needed to determine how well the techniques
described here transfer to other domains. However, the techniques we have developed, both forsmoothing and for analyzing smoothing algorithm performance, should prove useful not only for
language modeling research but for other tasks as well.

Acknowledgements
The authors would like to thank Stuart Shieber and the anonymous reviewers for their comments
on previous versions of this paper. This research was supported in part by the National Science
Foundation under Grant No. IRI-93-50192 and Grant No. CDA-94-01024. The second author was
also supported by Grant No. IRI-97-12068 and a National Science Foundation Graduate Student
Fellowship.

References
Bahl, Lalit R., Peter F. Brown, Peter V. de Souza, and Robert L. Mercer. 1989. A tree-based
statistical language model for natural language speech recognition. IEEE Transactions on
Acoustics, Speech and Signal Processing, 37:1001{1008, July.
Bahl, Lalit R., Frederick Jelinek, and Robert L. Mercer. 1983. A maximum likelihood approachto continuous speech recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-5(2):179{190, March.
Baum, L.E. 1972. An inequality and associated maximization technique in statistical estimationof probabilistic functions of a Markov process. Inequalities, 3:1{8.
60Bell, Timothy C., John G. Cleary, and Ian H. Witten. 1990. Text Compression. Prentice Hall,Englewood Cli s, N.J.
Brown, Peter F., John Cocke, Stephen A. Della Pietra, Vincent J. Della Pietra, Frederick Jelinek,
John D. La erty, Robert L. Mercer, and Paul S. Roossin. 1990. A statistical approach tomachine translation. Computational Linguistics, 16(2):79{85, June.
Brown, Peter F., Stephen A. Della Pietra, Vincent J. Della Pietra, Jennifer C. Lai, and Robert L.
Mercer. 1992a. An estimate of an upper bound for the entropy of English. Computational
Linguistics, 18(1):31{40, March.
Brown, Peter F., Vincent J. Della Pietra, Peter V. deSouza, Jennifer C. Lai, and Robert L. Mercer.
1992b. Class-based n-gram models of natural language. Computational Linguistics, 18(4):467{
479, December.
Chen, Stanley F. 1996. Building Probabilistic Models for Natural Language. Ph.D. thesis, Harvard
University, June.
Chen, Stanley F., Douglas Beeferman, and Ronald Rosenfeld. 1998. Evaluation metrics for language models. In DARPA Broadcast News Transcription and Understanding Workshop.
Chen, Stanley F. and Joshua T. Goodman. 1996. An empirical study of smoothing techniques
for language modeling. In Proceedings of the 34th Annual Meeting of the ACL, pages 310{318,Santa Cruz, California, June.
Church, Kenneth. 1988. A stochastic parts program and noun phrase parser for unrestricted
text. In Proceedings of the Second Conference on Applied Natural Language Processing, pages
136{143.
Church, Kenneth W. and William A. Gale. 1991. A comparison of the enhanced Good-Turing anddeleted estimation methods for estimating probabilities of English bigrams. Computer Speechand Language, 5:19{54.
Clarkson, P. and R. Rosenfeld. 1997. Statistical language modeling using the CMU-Cambridge
toolkit. In Proceedings of Eurospeech '97.
Collins, Michael and James Brooks. 1995. Prepositional phrase attachment through a backed-omodel. In David Yarowsky and Kenneth Church, editors, Proceedings of the Third Workshop
on Very Large Corpora, pages 27{38, Cambridge, MA, June.
Cover, Thomas M. and Joy A. Thomas. 1991. Elements of Information Theory. John Wiley.
DARPA. 1998. DARPA Broadcast News Transcription and Understanding Workshop.
Gale, William A. and Kenneth W. Church. 1990. Estimation procedures for language context:
poor estimates are worse than none. In COMPSTAT, Proceedings in Computational Statistics,
9th Symposium, pages 69{74, Dubrovnik, Yugoslavia, September.
Gale, William A. and Kenneth W. Church. 1994. What's wrong with adding one? In N. Oostdijk
and P. de Haan, editors, Corpus-Based Research into Language. Rodolpi, Amsterdam.
Gale, William A. and Geo rey Sampson. 1995. Good-Turing frequency estimation without tears.
Journal of Quantitative Linguistics, 2(3). To appear.
61

Godfrey, J.J., E.C. Holliman, and J. McDaniel. 1992. SWITCHBOARD: Telephone speech corpus
for research and development. In Proceedings of ICASSP-92, volume I, pages 517{520.
Good, I.J. 1953. The population frequencies of species and the estimation of population parameters. Biometrika, 40(3 and 4):237{264.
Goodman, Joshua. 1997. Probabilistic feature grammars. In Proceedings of the International
Workshop on Parsing Technologies 1997.
Hull, Jonathon. 1992. Combining syntactic knowledge and visual text recognition: A hidden
Markov model for part of speech tagging in a word recognition algorithm. In AAAI Symposium:
Probabilistic Approaches to Natural Language, pages 77{83.
Je reys, H. 1948. Theory of Probability. Clarendon Press, Oxford, second edition.
Jelinek, Frederick and Robert L. Mercer. 1980. Interpolated estimation of Markov source parameters from sparse data. In Proceedings of the Workshop on Pattern Recognition in Practice,
Amsterdam, The Netherlands: North-Holland, May.
Johnson, W.E. 1932. Probability: deductive and inductive problems. Mind, 41:421{423.
Katz, Slava M. 1987. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speech and Signal Processing,
ASSP-35(3):400{401, March.
Kernighan, M.D., K.W. Church, and W.A. Gale. 1990. A spelling correction program based on anoisy channel model. In Proceedings of the Thirteenth International Conference on Computational Linguistics, pages 205{210.
Kneser, Reinhard and Hermann Ney. 1995. Improved backing-o for m-gram language modeling. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal
Processing, volume 1, pages 181{184.
Kucera, H. and W.N. Francis. 1967. Computational Analysis of Present-Day American English.
Brown University Press, Providence R.I.
Lidstone, G.J. 1920. Note on the general case of the Bayes-Laplace formula for inductive or aposteriori probabilities. Transactions of the Faculty of Actuaries, 8:182{192.
MacKay, David J. C. and Linda C. Peto. 1995. A hierarchical Dirichlet language model. Natural
Language Engineering, 1(3):1{19.
Magerman, David M. 1994. Natural Language Parsing as Statistical Pattern Recognition. Ph.D.
thesis, Stanford University, February.
Marcus, M., B. Santorini, and M. Marcinkiewicz. 1993. Building a large annotated corpus ofEnglish: the Penn Treeback. Computational Linguistics, 19(2).
Markov, A.A. 1913. An example of statistical investigation in the text of `Eugene Onyegin'illustrating coupling of tests in chains. Proceedings of the Academy of Science, St. Petersburg,
7:153{162.

62Nadas, Arthur. 1984. Estimation of probabilities in the language model of the IBM speech
recognition system. IEEE Transactions on Acoustics, Speech and Signal Processing, ASSP32(4):859{861, August.
Ney, Hermann, Ute Essen, and Reinhard Kneser. 1994. On structuring probabilistic dependencesin stochastic language modeling. Computer, Speech, and Language, 8:1{38.
Placeway, P., S. Chen, M. Eskenazi, U. Jain, V. Parikh, B. Raj, M. Ravishankar, R. Rosenfeld,
K. Seymore, M. Siegler, R. Stern, and E. Thayer. 1997. The 1996 Hub-4 Sphinx-3 system. In
Proceedings of the DARPA Speech Recognition Workshop, February.
Press, W.H., B.P. Flannery, S.A. Teukolsky, and W.T. Vetterling. 1988. Numerical Recipes in C.
Cambridge University Press, Cambridge.
Ries, Klaus. 1997. personal communication.
Rogina, Ivica and Alex Waibel. 1995. The Janus speech recognizer. In ARPA SLT Workshop.
Rosenfeld, Ronald. 1995. The CMU statistical language modeling toolkit and its use in the 1994
ARPA CSR evaluation. In Proceedings of the Spoken Language Systems Technology Workshop,
pages 47{50, Austin, Texas, January.
Rudnicky, A.I. 1996. Hub 4: Business Broadcast News. In Proceedings of the DARPA Speech
Recognition Workshop, pages 8{11.
Seymore, K., S. Chen, M. Eskenazi, and R. Rosenfeld. 1997. Language and pronunciation modeling in the CMU 1996 Hub 4 evaluation. In Proceedings of the DARPA Speech Recognition
Workshop, Washington, D.C., February.
Srihari, Rohini and Charlotte Baltus. 1992. Combining statistical and syntactic methods inrecognizing handwritten sentences. In AAAI Symposium: Probabilistic Approaches to Natural
Language, pages 121{127.
Stern, Richard M. 1996. Speci cation of the 1995 ARPA hub 3 evaluation: Unlimited vocabulary
NAB news baseline. In Proceedings of the DARPA Speech Recognition Workshop, pages 5{7.
Weng, Fuliang, Andreas Stolcke, and Ananth Sankar. 1997. Hub4 language modeling using domaininterpolation and data clustering. In Proceedings of the DARPA Speech Recognition Workshop,
Washington, D.C., February.
Witten, Ian H. and Timothy C. Bell. 1991. The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression. IEEE Transactions on Information Theory,37(4):1085{1094, July.

63