Language Models
Philipp Koehn
11 September 2018
Philipp Koehn Machine Translation: Language Models 11 September 2018
1Language models
• Language models answer the question:
How likely is a string of English words good English?
• Help with reordering
pLM(the house is small) > pLM(small the is house)
• Help with word choice
pLM(I am going home) > pLM(I am going house)
Philipp Koehn Machine Translation: Language Models 11 September 2018
2N-Gram Language Models
• Given: a string of English words W = w1, w2, w3, ..., wn
• Question: what is p(W)?
• Sparse data: Many good English sentences will not have been seen before
→ Decomposing p(W) using the chain rule:
p(w1, w2, w3, ..., wn) = p(w1) p(w2|w1) p(w3|w1, w2)...p(wn|w1, w2, ...wn−1)
(not much gained yet, p(wn|w1, w2, ...wn−1) is equally sparse)
Philipp Koehn Machine Translation: Language Models 11 September 2018
3Markov Chain
• Markov assumption:
– only previous history matters
– limited memory: only last k words are included in history
(older words less relevant)
→ kth order Markov model
• For instance 2-gram language model:
p(w1, w2, w3, ..., wn) p(w1) p(w2|w1) p(w3|w2)...p(wn|wn−1)
• What is conditioned on, here wi−1 is called the history
Philipp Koehn Machine Translation: Language Models 11 September 2018
4Estimating N-Gram Probabilities
• Maximum likelihood estimation
p(w2|w1) =
count(w1, w2)
count(w1)
• Collect counts over a large text corpus
• Millions to billions of words are easy to get
(trillions of English words available on the web)
Philipp Koehn Machine Translation: Language Models 11 September 2018
5Example: 3-Gram
• Counts for trigrams and estimated word probabilities
the green (total: 1748)
word c. prob.
paper 801 0.458
group 640 0.367
light 110 0.063
party 27 0.015
ecu 21 0.012
the red (total: 225)
word c. prob.
cross 123 0.547
tape 31 0.138
army 9 0.040
card 7 0.031
, 5 0.022
the blue (total: 54)
word c. prob.
box 16 0.296
. 6 0.111
flag 6 0.111
, 3 0.056
angel 3 0.056
– 225 trigrams in the Europarl corpus start with the red
– 123 of them end with cross
→ maximum likelihood probability is 123
225 = 0.547.
Philipp Koehn Machine Translation: Language Models 11 September 2018
6How good is the LM?
• A good model assigns a text of real English W a high probability
• This can be also measured with cross entropy:
H(W) =
1
n
log p(Wn
1 )
• Or, perplexity
perplexity(W) = 2H(W )
Philipp Koehn Machine Translation: Language Models 11 September 2018
7Example: 3-Gram
prediction pLM -log2 pLM
pLM(i|</s><s>) 0.109 3.197
pLM(would|<s>i) 0.144 2.791
pLM(like|i would) 0.489 1.031
pLM(to|would like) 0.905 0.144
pLM(commend|like to) 0.002 8.794
pLM(the|to commend) 0.472 1.084
pLM(rapporteur|commend the) 0.147 2.763
pLM(on|the rapporteur) 0.056 4.150
pLM(his|rapporteur on) 0.194 2.367
pLM(work|on his) 0.089 3.498
pLM(.|his work) 0.290 1.785
pLM(</s>|work .) 0.99999 0.000014
average 2.634
Philipp Koehn Machine Translation: Language Models 11 September 2018
8Comparison 1–4-Gram
word unigram bigram trigram 4-gram
i 6.684 3.197 3.197 3.197
would 8.342 2.884 2.791 2.791
like 9.129 2.026 1.031 1.290
to 5.081 0.402 0.144 0.113
commend 15.487 12.335 8.794 8.633
the 3.885 1.402 1.084 0.880
rapporteur 10.840 7.319 2.763 2.350
on 6.765 4.140 4.150 1.862
his 10.678 7.316 2.367 1.978
work 9.993 4.816 3.498 2.394
. 4.896 3.020 1.785 1.510
</s> 4.828 0.005 0.000 0.000
average 8.051 4.072 2.634 2.251
perplexity 265.136 16.817 6.206 4.758
Philipp Koehn Machine Translation: Language Models 11 September 2018
9
count smoothing
Philipp Koehn Machine Translation: Language Models 11 September 2018
10Unseen N-Grams
• We have seen i like to in our corpus
• We have never seen i like to smooth in our corpus
→ p(smooth|i like to) = 0
• Any sentence that includes i like to smooth will be assigned probability 0
Philipp Koehn Machine Translation: Language Models 11 September 2018
11Add-One Smoothing
• For all possible n-grams, add the count of one.
p =
c + 1
n + v
– c = count of n-gram in corpus
– n = count of history
– v = vocabulary size
• But there are many more unseen n-grams than seen n-grams
• Example: Europarl 2-bigrams:
– 86, 700 distinct words
– 86, 7002
= 7, 516, 890, 000 possible bigrams
– but only about 30, 000, 000 words (and bigrams) in corpus
Philipp Koehn Machine Translation: Language Models 11 September 2018
12Add-α Smoothing
• Add α < 1 to each count
p =
c + α
n + αv
• What is a good value for α?
• Could be optimized on held-out set
Philipp Koehn Machine Translation: Language Models 11 September 2018
13What is the Right Count?
• Example:
– the 2-gram red circle occurs in a 30 million word corpus exactly once
→ maximum likelihood estimation tells us that its probability is 1
30,000,000
– ... but we would expect it to occur less often than that
• Question: How likely does a 2-gram that occurs once in a 30,000,000 word corpus
occur in the wild?
• Let’s find out:
– get the set of all 2-grams that occur once (red circle, funny elephant, ...)
– record the size of this set: N1
– get another 30,000,000 word corpus
– for each word in the set: count how often it occurs in the new corpus
(many occur never, some once, fewer twice, even fewer 3 times, ...)
– sum up all these counts (0 + 0 + 1 + 0 + 2 + 1 + 0 + ...)
– divide by N1 → that is our test count tc
Philipp Koehn Machine Translation: Language Models 11 September 2018
14Example: 2-Grams in Europarl
Count Adjusted count Test count
c (c + 1) n
n+v2 (c + α) n
n+αv2 tc
0 0.00378 0.00016 0.00016
1 0.00755 0.95725 0.46235
2 0.01133 1.91433 1.39946
3 0.01511 2.87141 2.34307
4 0.01888 3.82850 3.35202
5 0.02266 4.78558 4.35234
6 0.02644 5.74266 5.33762
8 0.03399 7.65683 7.15074
10 0.04155 9.57100 9.11927
20 0.07931 19.14183 18.95948
• Add-α smoothing with α = 0.00017
Philipp Koehn Machine Translation: Language Models 11 September 2018
15Deleted Estimation
• Estimate true counts in held-out data
– split corpus in two halves: training and held-out
– counts in training Ct(w1, ..., wn)
– number of ngrams with training count r: Nr
– total times ngrams of training count r seen in held-out data: Tr
• Held-out estimator:
ph(w1, ..., wn) =
Tr
NrN
where count(w1, ..., wn) = r
• Both halves can be switched and results combined
ph(w1, ..., wn) =
T1
r + T2
r
N(N1
r + N2
r )
where count(w1, ..., wn) = r
Philipp Koehn Machine Translation: Language Models 11 September 2018
16Good-Turing Smoothing
• Adjust actual counts r to expected counts r∗
with formula
r∗
= (r + 1)
Nr+1
Nr
– Nr number of n-grams that occur exactly r times in corpus
– N0 total number of n-grams
• Where does this formula come from? Derivation is in the textbook.
Philipp Koehn Machine Translation: Language Models 11 September 2018
17Good-Turing for 2-Grams in Europarl
Count Count of counts Adjusted count Test count
r Nr r∗
t
0 7,514,941,065 0.00015 0.00016
1 1,132,844 0.46539 0.46235
2 263,611 1.40679 1.39946
3 123,615 2.38767 2.34307
4 73,788 3.33753 3.35202
5 49,254 4.36967 4.35234
6 35,869 5.32928 5.33762
8 21,693 7.43798 7.15074
10 14,880 9.31304 9.11927
20 4,546 19.54487 18.95948
adjusted count fairly accurate when compared against the test count
Philipp Koehn Machine Translation: Language Models 11 September 2018
18
backoff and interpolation
Philipp Koehn Machine Translation: Language Models 11 September 2018
19Back-Off
• In given corpus, we may never observe
– Scottish beer drinkers
– Scottish beer eaters
• Both have count 0
→ our smoothing methods will assign them same probability
• Better: backoff to bigrams:
– beer drinkers
– beer eaters
Philipp Koehn Machine Translation: Language Models 11 September 2018
20Interpolation
• Higher and lower order n-gram models have different strengths and weaknesses
– high-order n-grams are sensitive to more context, but have sparse counts
– low-order n-grams consider only very limited context, but have robust counts
• Combine them
pI(w3|w1, w2) = λ1 p1(w3)
+ λ2 p2(w3|w2)
+ λ3 p3(w3|w1, w2)
Philipp Koehn Machine Translation: Language Models 11 September 2018
21Recursive Interpolation
• We can trust some histories wi−n+1, ..., wi−1 more than others
• Condition interpolation weights on history: λwi−n+1,...,wi−1
• Recursive definition of interpolation
pI
n(wi|wi−n+1, ..., wi−1) = λwi−n+1,...,wi−1
pn(wi|wi−n+1, ..., wi−1) +
+ (1 − λwi−n+1,...,wi−1
) pI
n−1(wi|wi−n+2, ..., wi−1)
Philipp Koehn Machine Translation: Language Models 11 September 2018
22Back-Off
• Trust the highest order language model that contains n-gram
pBO
n (wi|wi−n+1, ..., wi−1) =
=



αn(wi|wi−n+1, ..., wi−1)
if countn(wi−n+1, ..., wi) > 0
dn(wi−n+1, ..., wi−1) pBO
n−1(wi|wi−n+2, ..., wi−1)
else
• Requires
– adjusted prediction model αn(wi|wi−n+1, ..., wi−1)
– discounting function dn(w1, ..., wn−1)
Philipp Koehn Machine Translation: Language Models 11 September 2018
23Back-Off with Good-Turing Smoothing
• Previously, we computed n-gram probabilities based on relative frequency
p(w2|w1) =
count(w1, w2)
count(w1)
• Good Turing smoothing adjusts counts c to expected counts c∗
count∗
(w1, w2) ≤ count(w1, w2)
• We use these expected counts for the prediction model (but 0∗
remains 0)
α(w2|w1) =
count∗
(w1, w2)
count(w1)
• This leaves probability mass for the discounting function
d2(w1) = 1 −
w2
α(w2|w1)
Philipp Koehn Machine Translation: Language Models 11 September 2018
24Example
• Good Turing discounting is used for all positive counts
count p GT count α
p(big|a) 3 3
7 = 0.43 2.24 2.24
7 = 0.32
p(house|a) 3 3
7 = 0.43 2.24 2.24
7 = 0.32
p(new|a) 1 1
7 = 0.14 0.446 0.446
7 = 0.06
• 1 − (0.32 + 0.32 + 0.06) = 0.30 is left for back-off d2(a)
• Note: actual values for d2 is slightly higher, since the predictions of the lowerorder
model to seen events at this level are not used.
Philipp Koehn Machine Translation: Language Models 11 September 2018
25Diversity of Predicted Words
• Consider the bigram histories spite and constant
– both occur 993 times in Europarl corpus
– only 9 different words follow spite
almost always followed by of (979 times), due to expression in spite of
– 415 different words follow constant
most frequent: and (42 times), concern (27 times), pressure (26 times),
but huge tail of singletons: 268 different words
• More likely to see new bigram that starts with constant than spite
• Witten-Bell smoothing considers diversity of predicted words
Philipp Koehn Machine Translation: Language Models 11 September 2018
26Witten-Bell Smoothing
• Recursive interpolation method
• Number of possible extensions of a history w1, ..., wn−1 in training data
N1+(w1, ..., wn−1, •) = |{wn : c(w1, ..., wn−1, wn) > 0}|
• Lambda parameters
1 − λw1,...,wn−1 =
N1+(w1, ..., wn−1, •)
N1+(w1, ..., wn−1, •) + wn
c(w1, ..., wn−1, wn)
Philipp Koehn Machine Translation: Language Models 11 September 2018
27Witten-Bell Smoothing: Examples
Let us apply this to our two examples:
1 − λspite =
N1+(spite, •)
N1+(spite, •) + wn
c(spite, wn)
=
9
9 + 993
= 0.00898
1 − λconstant =
N1+(constant, •)
N1+(constant, •) + wn
c(constant, wn)
=
415
415 + 993
= 0.29474
Philipp Koehn Machine Translation: Language Models 11 September 2018
28Diversity of Histories
• Consider the word York
– fairly frequent word in Europarl corpus, occurs 477 times
– as frequent as foods, indicates and providers
→ in unigram language model: a respectable probability
• However, it almost always directly follows New (473 times)
• Recall: unigram model only used, if the bigram model inconclusive
– York unlikely second word in unseen bigram
– in back-off unigram model, York should have low probability
Philipp Koehn Machine Translation: Language Models 11 September 2018
29Kneser-Ney Smoothing
• Kneser-Ney smoothing takes diversity of histories into account
• Count of histories for a word
N1+(•w) = |{wi : c(wi, w) > 0}|
• Recall: maximum likelihood estimation of unigram language model
pML(w) =
c(w)
i c(wi)
• In Kneser-Ney smoothing, replace raw counts with count of histories
pKN(w) =
N1+(•w)
wi
N1+(•wi)
Philipp Koehn Machine Translation: Language Models 11 September 2018
30Modified Kneser-Ney Smoothing
• Based on interpolation
pBO
n (wi|wi−n+1, ..., wi−1) =
=



αn(wi|wi−n+1, ..., wi−1)
if countn(wi−n+1, ..., wi) > 0
dn(wi−n+1, ..., wi−1) pBO
n−1(wi|wi−n+2, ..., wi−1)
else
• Requires
– adjusted prediction model αn(wi|wi−n+1, ..., wi−1)
– discounting function dn(w1, ..., wn−1)
Philipp Koehn Machine Translation: Language Models 11 September 2018
31Formula for α for Highest Order N-Gram Model
• Absolute discounting: subtract a fixed D from all non-zero counts
α(wn|w1, ..., wn−1) =
c(w1, ..., wn) − D
w c(w1, ..., wn−1, w)
• Refinement: three different discount values
D(c) =



D1 if c = 1
D2 if c = 2
D3+ if c ≥ 3
Philipp Koehn Machine Translation: Language Models 11 September 2018
32Discount Parameters
• Optimal discounting parameters D1, D2, D3+ can be computed quite easily
Y =
N1
N1 + 2N2
D1 = 1 − 2Y
N2
N1
D2 = 2 − 3Y
N3
N2
D3+ = 3 − 4Y
N4
N3
• Values Nc are the counts of n-grams with exactly count c
Philipp Koehn Machine Translation: Language Models 11 September 2018
33Formula for d for Highest Order N-Gram Model
• Probability mass set aside from seen events
d(w1, ..., wn−1) =
i∈{1,2,3+} DiNi(w1, ..., wn−1•)
wn
c(w1, ..., wn)
• Ni for i ∈ {1, 2, 3+} are computed based on the count of extensions of a history
w1, ..., wn−1 with count 1, 2, and 3 or more, respectively.
• Similar to Witten-Bell smoothing
Philipp Koehn Machine Translation: Language Models 11 September 2018
34Formula for α for Lower Order N-Gram Models
• Recall: base on count of histories N1+(•w) in which word may appear, not raw
counts.
α(wn|w1, ..., wn−1) =
N1+(•w1, ..., wn) − D
w N1+(•w1, ..., wn−1, w)
• Again, three different values for D (D1, D2, D3+), based on the count of the
history w1, ..., wn−1
Philipp Koehn Machine Translation: Language Models 11 September 2018
35Formula for d for Lower Order N-Gram Models
• Probability mass set aside available for the d function
d(w1, ..., wn−1) =
i∈{1,2,3+} DiNi(w1, ..., wn−1•)
wn
c(w1, ..., wn)
Philipp Koehn Machine Translation: Language Models 11 September 2018
36Interpolated Back-Off
• Back-off models use only highest order n-gram
– if sparse, not very reliable.
– two different n-grams with same history occur once → same probability
– one may be an outlier, the other under-represented in training
• To remedy this, always consider the lower-order back-off models
• Adapting the α function into interpolated αI function by adding back-off
αI(wn|w1, ..., wn−1) = α(wn|w1, ..., wn−1)
+ d(w1, ..., wn−1) pI(wn|w2, ..., wn−1)
• Note that d function needs to be adapted as well
Philipp Koehn Machine Translation: Language Models 11 September 2018
37Evaluation
Evaluation of smoothing methods:
Perplexity for language models trained on the Europarl corpus
Smoothing method bigram trigram 4-gram
Good-Turing 96.2 62.9 59.9
Witten-Bell 97.1 63.8 60.4
Modified Kneser-Ney 95.4 61.6 58.6
Interpolated Modified Kneser-Ney 94.5 59.3 54.0
Philipp Koehn Machine Translation: Language Models 11 September 2018
38
efficiency
Philipp Koehn Machine Translation: Language Models 11 September 2018
39Managing the Size of the Model
• Millions to billions of words are easy to get
(trillions of English words available on the web)
• But: huge language models do not fit into RAM
Philipp Koehn Machine Translation: Language Models 11 September 2018
40Number of Unique N-Grams
Number of unique n-grams in Europarl corpus
29,501,088 tokens (words and punctuation)
Order Unique n-grams Singletons
unigram 86,700 33,447 (38.6%)
bigram 1,948,935 1,132,844 (58.1%)
trigram 8,092,798 6,022,286 (74.4%)
4-gram 15,303,847 13,081,621 (85.5%)
5-gram 19,882,175 18,324,577 (92.2%)
→ remove singletons of higher order n-grams
Philipp Koehn Machine Translation: Language Models 11 September 2018
41Efficient Data Structures
verythe large
boff:-0.385
majority p:-1.147
number p:-0.275
important
boff:-0.231
and p:-1.430
areas p:-1.728
challenge p:-2.171
debate p:-1.837
discussion p:-2.145
fact p:-2.128
international p:-1.866
issue p:-1.157
...
best
boff:-0.302
serious
boff:-0.146
very
very large
boff:-0.106
amount p:-2.510
amounts p:-1.633
and p:-1.449
area p:-2.658
companies p:-1.536
cuts p:-2.225
degree p:-2.933
extent p:-2.208
financial p:-2.383
foreign p:-3.428
...
important
boff:-0.250
best
boff:-0.082
serious
boff:-0.176
4-gram
3-gram backoff
large
boff:-0.470
accept p:-3.791
acceptable p:-3.778
accession p:-3.762
accidents p:-3.806
accountancy p:-3.416
accumulated p:-3.885
accumulation p:-3.895
action p:-3.510
additional p:-3.334
administration p:-3.729
...
2-gram backoff
aa-afns p:-6.154
aachen p:-5.734
aaiun p:-6.154
aalborg p:-6.154
aarhus p:-5.734
aaron p:-6.154
aartsen p:-6.154
ab p:-5.734
abacha p:-5.156
aback p:-5.876
...
1-gram backoff
• Need to store probabilities
for
– the very large majority
– the very language
number
• Both share history the very
large
→ no need to store history
twice
→ Trie
Philipp Koehn Machine Translation: Language Models 11 September 2018
42Reducing Vocabulary Size
• For instance: each number is treated as a separate token
• Replace them with a number token NUM
– but: we want our language model to prefer
pLM(I pay 950.00 in May 2007) > pLM(I pay 2007 in May 950.00)
– not possible with number token
pLM(I pay NUM in May NUM) = pLM(I pay NUM in May NUM)
• Replace each digit (with unique symbol, e.g., @ or 5), retain some distinctions
pLM(I pay 555.55 in May 5555) > pLM(I pay 5555 in May 555.55)
Philipp Koehn Machine Translation: Language Models 11 September 2018
43Summary
• Language models: How likely is a string of English words good English?
• N-gram models (Markov assumption)
• Perplexity
• Count smoothing
– add-one, add-α
– deleted estimation
– Good Turing
• Interpolation and backoff
– Good Turing
– Witten-Bell
– Kneser-Ney
• Managing the size of the model
Philipp Koehn Machine Translation: Language Models 11 September 2018