3

Language Models 1: n-gram Language Models

While the final goal of a statistical machine translation system is to create a model of thetarget sentence E given the source sentence F , P (E|F ), in this chapter we will take a step
back, and attempt to create a language model of only the target sentence P (E). Basically,
this model allows us to do two things that are of practical use.
Assess naturalness: Given a sentence E, this can tell us, does this look like an actual,natural sentence in the target language? If we can learn a model to tell us this, we canuse it to assess the fluency of sentences generated by an automated system to improve
its results, or even sentences generated by a human for purposes of grammar checking
or error correction.
Generate text: Language models can also be used to randomly generate text by samplinga sentence E 0 from the target distribution: E 0 ⇠ P (E) (where ⇠ means “is sampledfrom”). Randomly generating samples from a language model can be interesting in itself– we can see what the model “thinks” is a natural-looking sentences – but it will be
more practically useful in the context of the neural translation models described in thefollowing chapters.
In the following sections, we’ll cover a few methods used to calculate this probability P (E).

3.1

Word-by-word Computation of Probabilities

As mentioned above, we are interested in calculating the probability of a sentence E = eT1 .
Formally, this can be expressed as
P (E) = P (|E| = T, eT1 ),(3)

the joint probability that the length of the sentence is (|E| = T ), that the identity of thefirst word in the sentence is e1 , the identity of the second word in the sentence is e2 , up
until the last word in the sentence being eT . Unfortunately, directly creating a model ofthis probability distribution is not straightforward,3 as the length of the sequence T is notdetermined in advance, and there are a large number of possible combinations of words.4
As a way to make things easier, it is common to re-write the probability of the full sentence
as the product of single-word probabilities. This takes advantage of the fact that a joint
probability – for example P (e1 , e2 , e3 ) – can be calculated by multiplying together conditional
probabilities for each of its elements – in the example P (e1 , e2 , e3 ) = P (e1 )P (e2 |e1 )P (e3 |e1 , e2 ).
Figure 2 shows an example of this incremental calculation of probabilities for the sentence“she went home”. Here, in addition to the actual words in the sentence, we have introduced
an implicit sentence end (“h/si”) symbol, which we will indicate when we have terminated thesentence. Stepping through the equation in order, this means we first calculate the probabilityof “she” coming at the beginning of the sentence, then the probability of “went” coming next
in a sentence starting with “she”, the probability of “home” coming after the sentence prefix
3
4

Although it is possible, as shown by whole-sentence language models in [12].
Question: If V is the size of the target vocabulary, how many are there for a sentence of length T ?

5

P(|E| = 3, e1=”she”, e2=”went”, e3=”home”) =P(e1=“she”)* P(e2=”went” | e1=“she”)* P(e3=”home” | e1=“she”, e2=”went”)* P(e4=”
” | e1=“she”, e2=”went”, e3=”home”)
Figure 2: An example of decomposing language model probabilities word-by-word.

i am from pittsburgh .
i study at a university .
my mother is from utah .
P(e2=am | e1=i) = c(e1=i, e2=am)/c(e1=i) = 1 / 2 = 0.5
P(e2=study | e1=i) = c(e1=i, e2=study)/c(e1=i) = 1 / 2 = 0.5
Figure 3: An example of calculating probabilities for using maximum likelihood estimation.
“she went”, and then finally the sentence end symbol “h/si” after “she went home”. Moregenerally, we can express this as the following equation:
P (E) =TY+1
t=1

P (et |et1 1 )(4)where eT +1 = h/si. So coming back to the sentence end symbol h/si, the reason why weintroduced this is because it allows us to know when the sentence ends; the |E| = T term inour original LM joint probability in Equation 3. In this example, when we have h/si as the
4th word in the sentence, we know we’re done and our final sentence length is 3.
Once we have the formulation in Equation 4, the problem of language modeling now
becomes a problem of calculating the next word given the previous words P (et |et1 1 ). Thisis much more manageable than calculating the probability for the whole sentence, as we now
have a fixed set of items that we are looking to calculate probabilities for. The next coupleof sections will show a few ways to do so.

3.2

Count-based n-gram Language Models

The first way to calculate probabilities is simple: prepare a set of training data from which
we can count word strings, count up the number of times we have seen a particular string ofwords, and divide it by the number of times we have seen the context. This simple method,6

can be expressed by the equation below, with an example shown in Figure 3
PML (et |et1 1 ) =cprefix (et1 ).
cprefix (et1 1 )(5)Here cprefix (·) is the count of the number of times this particular word string appeared at the
beginning of a sentence in the training data. This approach is called maximum likelihood
estimation (MLE, details later in this chapter), and is both simple and guaranteed to createa model that assigns a high probability to the sentences in training data.
However, let’s say we want to use this model to assign a probability to a new sentencethat we’ve never seen before. For example, if we want to calculate the probability of thesentence “i am from utah .” based on the training data in the example. This sentence isextremely similar to the sentences we’ve seen before, but unfortunately because the string“i am from utah” has not been observed in our training data, cprefix (i, am, from, utah) = 0,
P (e4 = utah|e1 = i, e2 = am, e3 = from) becomes zero, and thus the probability of the wholesentence as calculated by Equation 5 also becomes zero. In fact, this language model willassign a probability of zero to every sentence that it hasn’t seen before in the training corpus,
which is not very useful, as the model loses ability to tell us whether a new sentence a systemgenerates is natural or not, or generate new outputs.
To solve this problem, we take two measures. First, instead of calculating probabilities
from the beginning of the sentence, we set a fixed window of previous words upon which wewill base our probability calculations, approximating the true probability. If we limit ourcontext to n 1 previous words, this would amount to:
P (et |et1 1 ) ⇡ PML (et |ett 1n+1 ).

(6)

Models that make this assumption are called n-gram models. Specifically, when models
where n = 1 are called unigram models, n = 2 bigram models, n = 3 trigram models, andn = 4 four-gram, five-gram, etc.
The parameters ✓ of n-gram models consist of probabilities of the next word given n 1
previous words:✓ett n+1 = P (et |ett 1n+1 ),(7)
and in order to train an n-gram model, we have to learn these parameters from data.5 In thesimplest form, these parameters can be calculated using maximum likelihood estimation as
follows:c(ett n+1 )✓ett n+1 = PML (et |ett 1n+1 ) =,(8)c(ett 1n+1 )where c(·) is the count of the word string anywhere in the corpus. Sometimes these equations
will reference et n+1 where t n + 1 < 0. In this case, we assume that et n+1 = hsi wherehsi is a special sentence start symbol.
If we go back to our previous example and set n = 2, we can see that while the string“i am from utah .” has never appeared in the training corpus, “i am”, “am from”, “fromutah”, “utah .”, and “. h/si” are all somewhere in the training corpus, and thus we can patch
together probabilities for them and calculate a non-zero probability for the whole sentence.6
5
6

Question: How many parameters does an n-gram model with a particular n have?
Question: What is this probability?

7However, we still have a problem: what if we encounter a two-word string that has neverappeared in the training corpus? In this case, we’ll still get a zero probability for thatparticular two-word string, resulting in our full sentence probability also becoming zero. ngram models fix this problem by smoothing probabilities, combining the maximum likelihood
estimates for various values of n. In the simple case of smoothing unigram and bigram
probabilities, we can think of a model that combines together the probabilities as follows:
P (et |et 1 ) = (1↵)PML (et |et 1 ) + ↵PML (et ),(9)where ↵ is a variable specifying how much probability mass we hold out for the unigram
distribution. As long as we set ↵ > 0, regardless of the context all the words in our vocabulary
will be assigned some probability. This method is called interpolation, and is one of thestandard ways to make probabilistic models more robust to low-frequency phenomena.
If we want to use even more context – n = 3, n = 4, n = 5, or more – we can recursively
define our interpolated probabilities as follows:
P (et |ett 1m+1 ) = (1↵m )PML (et |ett 1m+1 ) + ↵m P (et |ett 1m+2 ).

(10)

The first term on the right side of the equation is the maximum likelihood estimate for themodel of order m, and the second term is the interpolated probability for all orders up to
m 1.
There are also more sophisticated methods for smoothing, which are beyond the scope of
this section, but summarized very nicely in [6].
Context-dependent smoothing coefficients: Instead of having a fixed ↵, we condition
the interpolation coefficient on the context: ↵et 1 . This allows the model to givet m+1
more weight to higher order n-grams when there are a sufficient number of training
examples for the parameters to be estimated accurately and fall back to lower ordern-grams when there are fewer training examples. These context-dependent smoothingcoefficients can be chosen using heuristics [15] or learned from data [10].
Back-o↵: In Equation 9, we interpolated together two probability distributions over the full
vocabulary V . In the alternative formulation of back-o↵, the lower order distribution
only is used to calculate probabilities for words that were given a probability of zeroin the higher-order distribution. Back-o↵ is more expressive but also more complicatedthan interpolation, and the two have been reported to give similar results [7].
Modified distributions: It is also possible to use a di↵erent distribution than PML . Thiscan be done by subtracting a constant value from the counts before calculating probabilities, a method called discounting. It is also possible to modify the counts of lower
order-distributions to reflect the fact that they are used mainly as a fall-back for when
the higher-order distributions lack sufficient coverage.
Currently, Modified Kneser-Ney smoothing (MKN; [6]), is generally considered one of thestandard and e↵ective methods for smoothing n-gram language models. MKN uses contextdependent smoothing coefficients, discounting, and modification of lower-order distributions
to ensure accurate probability estimates.

8

3.3

Evaluation of Language Models

Once we have a language model, we will want to test whether it is working properly. The way
we test language models is, like many other machine learning models, but preparing threesets of data:
Training data is used to train the parameters ✓ of the model.
Development data is used to make choices between alternate models, or to tune the hyperparameters of the model. Hyper-parameters in the model above could include the maximum length of n in the n-gram model or the type of smoothing method.
Test data is used to measure our final accuracy and report results.
For language models, we basically want to know whether the model is an accurate modelof language, and there are a number of ways we can define this. The most straight-forward
way of defining accuracy is the likelihood of the model with respect to the development
or test data. The likelihood of the parameters ✓ with respect to this data is equal to theprobability that the model assigns to the data. For example, if we have a test dataset Etest ,this is:P (Etest ; ✓).
(11)
We often assume that this data consists of several independent sentences or documents E,
giving usY
P (Etest ; ✓) =P (E; ✓).
(12)
E2EtestAnother measure that is commonly used is log likelihoodX
log P (Etest ; ✓) =log P (E; ✓).

(13)

E2EtestThe log likelihood is used for a couple reasons. The first is because the probability of any
particular sentence according to the language model can be a very small number, and the
product of these small numbers can become a very small number that will cause numericalprecision problems on standard computing hardware. The second is because sometimes it ismore convenient mathematically to deal in log space. For example, when taking the derivativein gradient-based methods to optimize parameters (used in the next section), it is moreconvenient to deal with the sum in Equation 13 than the product in Equation 11.
It is also common to divide the log likelihood by the number of words in the corpus
X
length(Etest ) =
|E|.
(14)
E2EtestThis makes it easier to compare and contrast results across corpora of di↵erent lengths.
The final common measure of language model accuracy is perplexity, which is definedas the exponent of the average negative log likelihood per word
ppl(Etest ; ✓) = e (log P (Etest ;✓))/length(Etest ) .

(15)

An intuitive explanation of the perplexity is “how confused is the model about its decision?”
More accurately, it expresses the value “if we randomly picked words from the probability
9distribution calculated by the language model at each time step, on average how many words
would it have to pick to get the correct one?” One reason why it is common to see perplexities
in research papers is because the numbers calculated by perplexity are bigger, making thedi↵erences in models more easily perceptible by the human eye.7

3.4

Handling Unknown Words

Finally, one important point to keep in mind is that some of the words in the test set Etest
will not appear even once in the training set Etrain . These words are called unknown words,
and need to be handeled in some way. Common ways to do this in language models include:
Assume closed vocabulary: Sometimes we can assume that there will be no new words inthe test set. For example, if we are calculating a language model over ASCII characters,
it is reasonable to assume that all characters have been observed in the training set.
Similarly, in some speech recognition systems, it is common to simply assign a probability of zero to words that don’t appear in the training data, which means that thesewords will not be able to be recognized.
Interpolate with an unknown words distribution: As mentioned in Equation 10, we
can interpolate between distributions of higher and lower order. In the case of unknown words, we can think of this as a distribution of order “0”, and define the 1-gramprobability as the interpolation between the unigram distribution and unknown word
distribution
P (et ) = (1 ↵1 )PML (et ) + ↵1 Punk (et ).
(16)Here, Punk needs to be a distribution that assigns a probability to all words Vall , not justones in our vocabulary V derived from the training corpus. This could be done by, forexample, training a language model over characters that “spells out” unknown words inthe case they don’t exist in in our vocabulary. Alternatively, as a simpler approximationthat is nontheless fairer than ignoring unknown words, we can guess the total numberof words |Vall | in the language where we are modeling, where |Vall | > |V |, and define
Punk as a uniform distribution over this vocabulary: Punk (et ) = 1/|Vall |.
Add an hunki word: As a final method to handle unknown words we can remove some of
the words in Etrain from our vocabulary, and replace them with a special hunki symbol
representing unknown words. One common way to do so is to remove singletons, orwords that only appear once in the training corpus. By doing this, we explicitly predictin which contexts we will be seeing an unknown word, instead of implicitly predicting
it through interpolation like mentioned above. Even if we predict the hunki symbol, we
will still need to estimate the probability of the actual word, so any time we predicthunki at position i, we further multiply in the probability of Punk (et ).

3.5

Further Reading

To read in more detail about n-gram language models, [7] gives a very nice introduction andcomprehensive summary about a number of methods to overcome various shortcomings ofvanilla n-grams like the ones mentioned above.
7

And, some cynics will say, making it easier for your research papers to get accepted.

10There are also a number of extensions to n-gram models that may be nice for the interested
reader.
Large-scale language modeling: Language models are an integral part of many commercial applications, and in these applications it is common to build language models using
massive amounts of data harvested from the web for other sources. To handle this data,
there is research on efficient data structures [8, 11], distributed parameter servers [5],and lossy compression algorithms [14].
Language model adaptation: In many situations, we want to build a language model for
specific speaker or domain. There are a number of language model adaptation
techniques, which make it possible to create large general-purpose models, then adapt
these models to more closely match the target use case [3].
Longer-distance language count-based models: As mentioned above, n-gram models
limit their context to n 1, but in reality there are dependencies in language thatcan reach much farther back into the sentence, or even span across whole documents.
The recurrent neural network language models that we will introduce in Section 6 are
one way to handle this problem, but there are also non-neural approaches such as cachelanguage models [9], topic models [4], and skip-gram models [7].
Syntax-based language models: There are also models that take into account the syntaxof the target sentence. For example, it is possible to condition probabilities not onwords that occur directly next to each other in the sentence, but those that are “close”
syntactically [13].

3.6

Exercise

The exercise that we will be doing in class will be constructing an n-gram LM with linear
interpolation between various levels of n-grams. We will write code to:• Read in and save the training and testing corpora.
• Learn the parameters on the training corpus by counting up the number of times eachn-gram has been seen, and calculating maximum likelihood estimates according to Equation 8.
• Calculate the probabilities of the test corpus using linearly interpolation according toEquation 9 or Equation 10.
To handle unknown words, you can use the uniform distribution method described in Section 3.4, assuming that there are 10,000,000 words in the English vocabulary. As a sanity
check, it may be better to report the number of unknown words, and which portions of the
per-word log-likelihood were incurred by the main model, and which portion was incurred by
the unknown word probability log Punk .
Potential improvements to the model include reading [6] and implementing a bettersmoothing method, implementing a better method for handling unknown words, or implementing one of the more advanced methods in Section 3.5.

11

Chapter 3 References[3] Jerome R Bellegarda. Statistical language model adaptation: review and perspectives. Speechcommunication, 42(1):93–108, 2004.
[4] David M. Blei, Andrew Y. Ng, and Michael I. Jordan. Latent Dirichlet allocation. Journal of
Machine Learning Research, 3, 2003.
[5] Thorsten Brants, Ashok C. Popat, Peng Xu, Franz J. Och, and Je↵rey Dean. Large language models in machine translation. In Proceedings of the 2007 Joint Conference on Empirical Methods in
Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL),
pages 858–867, 2007.
[6] Stanley F. Chen and Joshua Goodman. An empirical study of smoothing techniques for language modeling. In Proceedings of the 34th Annual Meeting of the Association for Computational
Linguistics (ACL), pages 310–318, 1996.
[7] Joshua T. Goodman. A bit of progress in language modeling. Computer Speech & Language,15(4):403–434, 2001.
[8] Kenneth Heafield. Kenlm: Faster and smaller language model queries. In Proceedings of the 6thWorkshop on Statistical Machine Translation (WMT), pages 187–197, 2011.
[9] Roland Kuhn and Renato De Mori. A cache-based natural language model for speech recognition.
IEEE transactions on pattern analysis and machine intelligence, 12(6):570–583, 1990.
[10] Graham Neubig and Chris Dyer. Generalizing and hybridizing count-based and neural language
models. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2016.
[11] Adam Pauls and Dan Klein. Faster and smaller n-gram language models. pages 258–267, 2011.
[12] Ronald Rosenfeld, Stanley F Chen, and Xiaojin Zhu. Whole-sentence exponential language models: a vehicle for linguistic-statistical integration. Computer Speech & Language, 15(1):55–73,
2001.
[13] Libin Shen, Jinxi Xu, and Ralph Weischedel. A new string-to-dependency machine translation
algorithm with a target dependency language model. In Proceedings of the 46th Annual Meetingof the Association for Computational Linguistics (ACL), pages 577–585, 2008.
[14] David Talbot and Thorsten Brants. Randomized language models via perfect hash functions. In
Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics (ACL),
pages 505–513, 2008.
[15] I.H. Witten and T.C. Bell. The zero-frequency problem: Estimating the probabilities of novel
events in adaptive text compression. Information Theory, IEEE Transactions on, 37(4):1085–
1094, 1991.

12