1
00:00:00,242 --> 00:00:03,442
Let’s talk about Kneser-Ney Smoothing,
2
00:00:03,442 --> 00:00:05,458
one of the most sophisticated forms of smoothing,
3
00:00:05,458 --> 00:00:08,334
but also one with a beautiful and elegant intuition.
4
00:00:09,765 --> 00:00:14,459
Remember that from Good-Turing, we talked about the c’s,
5
00:00:14,459 --> 00:00:17,194
the discounted counts you end up from Good-Turing,
6
00:00:17,194 --> 00:00:22,191
and we discounted each of the counts —
7
00:00:22,191 --> 00:00:24,412
the count of one was discounted to point four,
8
00:00:24,412 --> 00:00:27,682
and the count of two discounted to 1.26 and so on —
9
00:00:27,682 --> 00:00:32,564
in order to save mass to replace the zero counts with some low number.
10
00:00:32,564 --> 00:00:39,421
And if you look at the actual values of these counts — 8.25 for nine and 7.24 for eight —
11
00:00:39,421 --> 00:00:41,621
you’ll notice that in a very large number of cases,
12
00:00:41,621 --> 00:00:47,559
the discounted count has a very close relationship with the original count.
13
00:00:47,559 --> 00:00:52,856
It’s really the original count minus .75, or somewhat close to that.
14
00:00:52,856 --> 00:01:01,361
So, in practice what Good-Turing often does is produce a fixed small discount from the counts.
15
00:01:01,361 --> 00:01:07,590
And that intuition, that of a fixed small discount, can be applied directly.
16
00:01:07,590 --> 00:01:12,807
When we do this, we call this absolute discounting, and absolute discounting is a popular kind of smoothing.
17
00:01:12,807 --> 00:01:17,548
And here we’re showing you absolute discounting interpolation.
18
00:01:17,548 --> 00:01:22,372
And again, the intuition is just: We’ll save some time and have to compute all those complicated Good-Turing numbers
19
00:01:22,372 --> 00:01:27,962
and we’ll just subtract .75, or maybe it will be a different discount value for different corpora.
20
00:01:27,962 --> 00:01:30,032
Now here’s the equation for absolute discounting.
21
00:01:30,032 --> 00:01:31,900
So we’re doing diagrams again.
22
00:01:31,900 --> 00:01:37,464
So the probability, absolute discounted, of a word, given the previous word,
23
00:01:37,464 --> 00:01:44,173
will be some discounted bigram, interpolated with some interpolation weight, with the unigram probability.
24
00:01:44,173 --> 00:01:47,905
So we have a unigram probability P(w), and then the bigram probability,
25
00:01:47,905 --> 00:01:53,402
and we just subtract a fixed amount, let’s say it’s .75, from the count.
26
00:01:53,402 --> 00:01:56,962
And otherwise compute the bigram probability in the normal way.
27
00:01:56,962 --> 00:02:00,136
So, we have a discounted bigram probability, mixed with some weight,
28
00:02:00,136 --> 00:02:03,103
which I shall talk later about how to set this weight, with a unigram.
29
00:02:03,103 --> 00:02:07,701
And maybe we might keep a couple of extra values of d for counts one and two.
30
00:02:07,701 --> 00:02:12,701
Counts one and two, we saw on a previous slide, weren’t quite subtracting .75,
31
00:02:12,701 --> 00:02:16,316
so we can model this more carefully by having separate counts for those.
32
00:02:17,239 --> 00:02:22,558
But the problem with absolute discounting is the unigram probability itself.
33
00:02:22,558 --> 00:02:25,688
And I want to talk about changing the unigram probability.
34
00:02:25,688 --> 00:02:28,236
And that’s the fundamental intuition of Kneser-Ney.
35
00:02:28,236 --> 00:02:34,501
So in Kneser-Ney smoothing, the idea is keep that same interpolation that we saw in absolute discounting,
36
00:02:34,501 --> 00:02:38,557
but use a better estimate of probabilities of the lower unigrams.
37
00:02:38,557 --> 00:02:42,671
And the intuition for that, we can go back and look at the classic Shannon games.
38
00:02:42,671 --> 00:02:45,573
Remember, in the Shannon game we’re predicting a word from previous words,
39
00:02:45,573 --> 00:02:49,960
so we see a sentence, “I can’t see without my reading .”
40
00:02:49,960 --> 00:02:51,375
What’s the most likely next word?
41
00:02:51,375 --> 00:02:52,879
Well, “glasses” seems pretty likely.
42
00:02:52,879 --> 00:02:56,226
Well, how about instead the word “Francisco”?
43
00:02:56,226 --> 00:02:58,886
Well, that seems very unlikely in this situation.
44
00:02:58,886 --> 00:03:04,907
And yet “Francisco”, as just a unigram, is more common than “glasses”.
45
00:03:04,907 --> 00:03:10,670
But the reason why “Francisco” seems like a bad thing after “reading”,
46
00:03:10,670 --> 00:03:16,404
one intuition we might be able to get is that “Francisco” always follows “San” or very often follows “San”.
47
00:03:16,404 --> 00:03:21,627
So while “Francisco” is very frequent, it’s frequent in the context of the word “San”.
48
00:03:21,627 --> 00:03:26,168
Now, unigrams in an interpolation model, where we’re mixing a unigram and a bigram,
49
00:03:26,168 --> 00:03:31,230
are specifically useful — they’re very helpful — just in case where we haven’t seen a bigram.
50
00:03:31,230 --> 00:03:37,158
So it’s unfortunate that just in the case where we haven’t seen the bigram “reading Francisco”,
51
00:03:37,158 --> 00:03:41,214
we’re trusting “Francisco”’s unigram weight which is just where we shouldn’t trust it.
52
00:03:41,214 --> 00:03:45,582
So instead of using the probability of w, how likely is a word,
53
00:03:45,582 --> 00:03:48,518
our intuition is going to be when we’re backing off to something
54
00:03:48,518 --> 00:03:51,523
we should instead use the continuation probability.
55
00:03:51,523 --> 00:03:53,730
We’re going to call it P continuation of a word,
56
00:03:53,730 --> 00:03:57,164
how likely is the word to appear as a novel continuation.
57
00:03:57,164 --> 00:03:59,453
Well, how do we measure novel continuation?
58
00:03:59,453 --> 00:04:04,067
Well, for each word we’ll just count the number of bigram types it completes.
59
00:04:04,067 --> 00:04:08,863
How many different bigrams does it create by appearing after another word.
60
00:04:08,863 --> 00:04:14,243
In other words, each bigram type is a novel continuation the first time we see this new bigram.
61
00:04:14,243 --> 00:04:21,202
In other words, the continuation probability is going to be proportional to the cardinality of this set,
62
00:04:21,202 --> 00:04:27,875
the number of words of preceding words, i minus one, that occur with our word.
63
00:04:27,875 --> 00:04:33,292
So, how many words occur before this word in a bigram.
64
00:04:33,292 --> 00:04:34,985
How many preceding words are there.
65
00:04:34,985 --> 00:04:41,792
That will be the cardinality of that set, that’s a number we would like our continuation probability to be proportional to.
66
00:04:41,792 --> 00:04:45,554
So how many times does w appear as a novel continuation?
67
00:04:45,554 --> 00:04:47,450
We need to turn that into a probability.
68
00:04:47,450 --> 00:04:50,967
So we just divide by the total number of word bigram types.
69
00:04:50,967 --> 00:04:58,648
So, of all word bigrams that occur more than zero times, what’s the cardinality of that set?
70
00:04:58,648 --> 00:05:00,741
How many different word bigram types are there,
71
00:05:00,741 --> 00:05:05,552
and we’re just going to divide the two to get a probability of continuation,
72
00:05:05,552 --> 00:05:11,465
of all the number of word bigram types how many of those have w as a novel continuation.
73
00:05:11,465 --> 00:05:16,604
Now it turns out that there’s an alternative metaphor for Kneser-Ney with the same equations
74
00:05:16,604 --> 00:05:23,543
so again we can see the numerator as the total number of word types that precede w,
75
00:05:23,543 --> 00:05:30,304
how many word types can w follow and we’re going to normalize it by the number of words that could precede all words.
76
00:05:30,304 --> 00:05:36,865
So, this sum over all words of the number of word types that can precede the word.
77
00:05:36,865 --> 00:05:39,656
And these two are the same:
78
00:05:39,656 --> 00:05:45,180
The number of this denominator and the denominator we saw on the previous slide are the same
79
00:05:45,180 --> 00:05:53,846
because the number of possible bigram types is the same as the number of word type that can precede all words summed over all words.
80
00:05:53,846 --> 00:05:56,470
If you think about that for a second, you’ll realize that’s true.
81
00:05:56,470 --> 00:06:00,159
So in other words, with this kind of Kneser-Ney model,
82
00:06:00,159 --> 00:06:08,261
a frequent word like “Francisco” that occurs only in one context like “San” will have a low continuation probability.
83
00:06:08,261 --> 00:06:15,602
So if we put together the intuition of absolute discounting with the Kneser-Ney probability for the lower order n-gram,
84
00:06:15,602 --> 00:06:18,809
we have the Kneser-Ney smoothing algorithm.
85
00:06:18,809 --> 00:06:24,794
So, for the bigram itself we just have absolute discounting —
86
00:06:24,794 --> 00:06:28,299
We take the bigram count, we subtract some d discount,
87
00:06:28,299 --> 00:06:31,417
and I’ve just shown here that we take the max of that and zero
88
00:06:31,417 --> 00:06:35,511
because, obviously, if the discount happens to be higher than the probability we don’t want a negative probability.
89
00:06:35,511 --> 00:06:40,345
And we’re just gonna interpolate that with this same continuation probability that we just saw,
90
00:06:40,345 --> 00:06:44,230
p continuation of w sub i.
91
00:06:44,230 --> 00:06:47,360
And, the lambda, now let’s talk about how to compute that lambda.
92
00:06:47,360 --> 00:06:54,114
The lambda is gonna take all that probability mass from all those normalized discounts
93
00:06:54,114 --> 00:06:56,232
that we took out of these higher-order probabilities,
94
00:06:56,232 --> 00:07:02,580
and use those to weight how much probability we should assign to the unigram.
95
00:07:02,580 --> 00:07:05,673
We’re gonna combine those.
96
00:07:05,673 --> 00:07:13,698
So that lambda is the amount of the discount weight divided by the denominator there.
97
00:07:13,698 --> 00:07:15,965
So, it’s the normalized discount.
98
00:07:15,965 --> 00:07:23,030
And then, we’re gonna multiply that by the total number of word types that can follow this context, wi minus one.
99
00:07:23,030 --> 00:07:27,300
In other words, how many different word types did we discount
100
00:07:27,300 --> 00:07:30,076
or how many times did we apply this normalized discount.
101
00:07:30,076 --> 00:07:31,867
And we multiply those together
102
00:07:31,867 --> 00:07:37,409
and we know how much probably mass total we can now assign to the continuation of the word.
103
00:07:37,409 --> 00:07:40,659
Now, this is the bigram formulation for Kneser-Ney.
104
00:07:40,659 --> 00:07:46,173
Now in this slide, we’re showing you the general recursive formulation for n-grams in general,
105
00:07:46,173 --> 00:07:51,365
and here we have to make a slight change to deal with all the higher-order n-grams.
106
00:07:51,365 --> 00:07:55,603
So here we’re just showing the Kneser-Ney probability of a word given the prefix of the word.
107
00:07:55,603 --> 00:07:57,662
And, just like Kneser-Ney we saw before,
108
00:07:57,662 --> 00:08:06,809
we’re just interpolating a higher-order n-gram which is discounted with a lambda weight and a lower-order probability.
109
00:08:06,809 --> 00:08:14,940
But now we need to distinguish between the very first top-level time that we use a count and these lower order counts.
110
00:08:14,940 --> 00:08:20,107
So we’re going to use the actual count for the very highest order bigram,
111
00:08:20,107 --> 00:08:25,859
and we’re going to use the continuation value that we just defined earlier for all the lower order probabilities.
112
00:08:25,859 --> 00:08:33,052
So we’ll define this new thing count Kneser-Ney of dot which will mean actual count.
113
00:08:33,052 --> 00:08:35,763
This will be actual count, let’s say we’re doing trigrams.
114
00:08:35,763 --> 00:08:41,589
For the trigram, and then when we recurse and have the Kneser-Ney probability for the lower order things.
115
00:08:41,589 --> 00:08:44,607
When we get down to the bigrams and unigrams, we’ll be using the continuation count,
116
00:08:44,607 --> 00:08:49,216
that’s again the single word context that we defined earlier.
117
00:08:49,216 --> 00:08:51,720
So Kneser-Ney smoothing, a very excellent algorithm.
118
00:08:51,720 --> 00:08:54,743
It’s very commonly used in speech recognition and machine translation
119
00:08:54,743 --> 99:59:59,000
and yet it has a very beautiful and elegant intuition and I hope you appreciate it.