1 00:00:01,520 --> 00:00:07,134 We're ready to talk now about advanced methods of smoothing. Remember the add one 2 00:00:07,134 --> 00:00:12,965 smoothing that we had earlier. In add one smoothing we add one to the numerator and 3 00:00:12,965 --> 00:00:18,518 V to the denominator. Then we saw a generalization of that, at K smoothing, 4 00:00:18,518 --> 00:00:25,108 where we added K to the numerator, and kV to the denominator. And we can modify that 5 00:00:25,108 --> 00:00:31,222 slightly, we can create a new version, where we simply replace, introduce a new 6 00:00:31,222 --> 00:00:37,494 term, a new variable m=KV. And now we have a new way of writing add k smoothing that 7 00:00:37,494 --> 00:00:43,688 is going to be a helpful way of writing it. And the reason is, let's see on the 8 00:00:43,688 --> 00:00:49,145 next slide, that when we write. Write it this way, we can that what we're doing is 9 00:00:49,145 --> 00:00:54,836 adding to every. By gram we are adding a constant that's related to one over 10 00:00:54,836 --> 00:01:00,793 the vocabulary size. And instead of doing that we could add a constant related to 11 00:01:00,793 --> 00:01:06,898 the uni gram probability of the word that are backing off to. So the uni gram prior 12 00:01:06,898 --> 00:01:13,075 smoothing algorithm is a is an extension to add K that says instead of using one over V as 13 00:01:13,075 --> 00:01:18,736 our... to add to every adding some function of one over V to every bigram 14 00:01:18,736 --> 00:01:24,584 count, let's add something about the unigram probability. So, really, unigram prior is 15 00:01:24,584 --> 00:01:29,882 a kind of interpolation. It's, it's a variant of interpolation where we're 16 00:01:29,882 --> 00:01:35,317 adding the count and, in some function of the unigram probability to the bigram 17 00:01:35,317 --> 00:01:45,733 count. Nonetheless, although unigram prior smoothing works well, it still doesn't 18 00:01:45,733 --> 00:01:55,340 work well enough to be used for language modeling. Instead, the intuition used by 19 00:01:55,340 --> 00:01:59,709 many smoothing algorithms, Good-Turing smoothing, Kneser-Ney smoothing, Witten- 20 00:01:59,709 --> 00:02:04,021 Bell smoothing, is to use the count of things we've seen once to estimate the 21 00:02:04,021 --> 00:02:08,558 count of things we've never seen. The goal of a smoothing algorithm is to replace 22 00:02:08,558 --> 00:02:13,095 those unseen zeroes with something else. And all these algorithms say, look at the 23 00:02:13,095 --> 00:02:17,688 things you've seen once. Things that you saw once before are just like things that 24 00:02:17,688 --> 00:02:22,001 you haven't seen yet. And then you're gonna seem them once in the test set. So 25 00:02:22,001 --> 00:02:26,465 to see how this intuition works, we're gonna introduce some notation. And we're 26 00:02:26,465 --> 00:02:31,840 gonna, the notation we're gonna introduce is, big N, sub C. And that will mean the 27 00:02:31,840 --> 00:02:37,084 frequency of frequency C, meaning how many things occurred with frequency C. How 28 00:02:37,084 --> 00:02:42,393 big is the bin of things that occurred with frequency C. And that's hard to, to, 29 00:02:42,393 --> 00:02:47,929 it's not very intuitive. So let's look at some intuitions. So let's take a little 30 00:02:47,929 --> 00:02:53,796 sentence. Sam I am, I am Sam. I do not eat. And let's just look at the unigram 31 00:02:53,796 --> 00:02:59,663 count in there. So we have I occuring three times, Sam occuring twice, and do, 32 00:02:59,663 --> 00:03:06,643 not, and eat occuring once each time. So what is N sub one? How many things occur 33 00:03:06,643 --> 00:03:13,021 one time? Well, here they are, there are three of them. Three different word types 34 00:03:13,021 --> 00:03:19,641 occur one time. So N sub one is three. How'bout, how many things occur two 35 00:03:19,641 --> 00:03:26,474 times? Well, there's two of those. So N sub two is two. And how'bout things that 36 00:03:26,474 --> 00:03:31,830 occur three times, well only one of those happens. So N sum three is one. Alright, 37 00:03:31,830 --> 00:03:36,847 so now that we have the intuition about how to think about frequencies of 38 00:03:36,847 --> 00:03:42,067 frequencies, let's apply this to get the intuition for Good-Turing smoothing. 39 00:03:42,067 --> 00:03:47,355 Imagine you're fishing, this is a scenario invented by Josh Goodman, and you've 40 00:03:47,355 --> 00:03:52,168 caught ten carp, three perch, two whitefish, one trout, one salmon, and one 41 00:03:52,168 --> 00:03:57,250 eel. I don't know what kind of river or stream or ocean this could be, but 42 00:03:57,250 --> 00:04:02,387 nonetheless, you've caught eighteen fish. And I, we want to estimate how likely is 43 00:04:02,387 --> 00:04:07,589 it the next species is trout. And this is like words. We have maybe a word that's occurred 44 00:04:07,589 --> 00:04:12,469 ten times or three, or two, or one. We want to know how likely are these 1s to 45 00:04:12,469 --> 00:04:18,831 occur again. Well, there's been eighteen fish. The trout's occurred one time out of 46 00:04:18,831 --> 00:04:24,443 eighteen. So, the probability ought to be one out of eighteen. But now, let's ask 47 00:04:24,443 --> 00:04:29,171 how likely is it that the next species is a new species, catfish or bass, some 48 00:04:29,171 --> 00:04:33,837 species that we haven't seen before. Something that occurred zero times. Well 49 00:04:33,837 --> 00:04:38,749 the Good-Turing intuition says let's use our estimate of things we saw once to 50 00:04:38,749 --> 00:04:43,845 estimate these new things we've never seen before. So what's our estimate of things 51 00:04:43,845 --> 00:04:48,978 once? Our estimate of things once is drawn from N sub one, how many things occurred 52 00:04:48,978 --> 00:04:54,189 once? Well, what's N sub one? N sub one is three. So out of the eighteen things we 53 00:04:54,189 --> 00:04:59,466 saw, three of them were new, were things that only occurred one time. So let's use 54 00:04:59,466 --> 00:05:04,941 three out of eighteen as our estimate for things that, that we've never seen before. 55 00:05:04,941 --> 00:05:10,416 We're going to use our estimate of things, our count of things that we've seen once 56 00:05:10,416 --> 00:05:15,891 as our estimate of things that we've never seen before. We're going to reserve some 57 00:05:15,891 --> 00:05:21,494 probability mass for all those unseen things. Well now, if we do that, if we use 58 00:05:21,701 --> 00:05:27,354 three out of eighteen as our estimate for all the unseen things we could possibly 59 00:05:27,354 --> 00:05:32,026 see, how likely is it the next species is trout? Well I already asked you that 60 00:05:32,026 --> 00:05:36,602 question. But before I said one over eighteen, but that can't be true anymore. 61 00:05:36,602 --> 00:05:41,540 It must be less than one over eighteen because we've used some of our probability 62 00:05:41,540 --> 00:05:46,358 mass for the, from the original eighteen fish. We've saved some of that for these 63 00:05:46,358 --> 00:05:51,236 new fish that we've never seen before. We've removed 3/18 of our probability mass 64 00:05:51,236 --> 00:05:56,355 and so we now have to, have to discount all of our probabilities for the other fish 65 00:05:56,355 --> 00:06:05,203 downward a little bit. How are we gonna estimate what this discount factor is? How 66 00:06:05,203 --> 00:06:12,900 much should we reduce all of these counts. Here's the, equation for Good-Turing. 67 00:06:12,900 --> 00:06:18,680 Here's the answer to that question. Good-Turing tells us that the probability for 68 00:06:18,680 --> 00:06:23,916 things that we've never seen before, p star for things with zero frequency, is 69 00:06:23,916 --> 00:06:29,221 exactly what we used on the previous slide. N sub one, the count of things that 70 00:06:29,221 --> 00:06:34,593 have occurred with frequency one, over N. So it's just a, that's, we saw three out 71 00:06:34,593 --> 00:06:39,830 of eighteen was our number. Well, then, what do you do with, with things that 72 00:06:39,830 --> 00:06:44,867 didn't occur with zero frequency and for that we use the second part of the 73 00:06:44,867 --> 00:06:49,716 Good-Turing equation, which says the new count, C star, the Good-Turing count, is 74 00:06:49,716 --> 00:06:55,025 going to be N sub-C plus one divided N sub-C, times C plus one. So, let's just 75 00:06:55,025 --> 00:06:59,797 work that out, and we'll, we'll, we'll, give you an intuition for why this is in a 76 00:06:59,797 --> 00:07:04,750 second, let's work out the, work it out in an example first. So, unseen fish, let's 77 00:07:04,750 --> 00:07:09,583 say it's bass or catfish we haven't seen before, in the training set, the maximum 78 00:07:09,583 --> 00:07:14,113 likelihood probability, estimated probability is zero. We didn't see this in 79 00:07:14,113 --> 00:07:18,764 the training set out of zero words, so it's zero out of eighteen or it's zero. 80 00:07:18,764 --> 00:07:24,107 But smoothed, we're gonna use the new good touring probability. And that says its' n1 81 00:07:24,107 --> 00:07:30,059 out of n, n1 is three. We saw three things once on a previous slide out of eighteen 82 00:07:30,059 --> 00:07:35,725 things. And so the new probability is going to be 3/18. What about for something 83 00:07:35,725 --> 00:07:40,963 we've seen once, like trout? How are we gonna re-estimate the trout? Well, the 84 00:07:40,963 --> 00:07:46,549 maximum likelihood estimate tells us that there was the count of one. And so the 85 00:07:46,549 --> 00:07:52,485 maximum likelihood probability is one over eighteen. But the new good touring formula 86 00:07:52,485 --> 00:07:58,071 here says the count of trout should be C, C is one, C+1, so two times N sub two over 87 00:07:58,071 --> 00:08:04,518 N sub one. And that's going to be two x one-third, because n sub two is one from 88 00:08:04,518 --> 00:08:11,100 the previous slide, and n sub one is three, and two x one-third, so two-thirds. 89 00:08:11,100 --> 00:08:17,719 So our Good-Turing probability takes our c star from trout. And, and, and divides 90 00:08:17,719 --> 00:08:23,352 it by the eighteen things we've seen so it's two thirds slash eighteen or 1/27. 91 00:08:23,352 --> 00:08:29,125 So instead of the count of things we saw once before we had one over eighteen and 92 00:08:29,125 --> 00:08:34,048 now we've dropped it to two thirds. Two-thirds over eighteen. So we've 93 00:08:34,048 --> 00:08:39,690 discounted our probability from 1/18 to only two-thirds of an eighteenth, and we've 94 00:08:39,690 --> 00:08:45,548 used that extra discounted probability mass to account for the zero things we've 95 00:08:45,548 --> 00:08:53,012 never seen before. [sound] Let's look at the nice intuition for Good-Turing 96 00:08:53,012 --> 00:08:57,653 development by Herman Ney and his colleagues. Imagine the training set, this 97 00:08:57,653 --> 00:09:02,720 is of size c, and this would be a training set with words in it. This is a word, this 98 00:09:02,720 --> 00:09:07,360 is another word, here's another word, here's another word. And now let's, we're 99 00:09:07,360 --> 00:09:11,862 going to hold out iteratively words from this training set. Let's first take one 100 00:09:11,862 --> 00:09:15,912 word, that first word there, the blue word, and we'll just write it over here. 101 00:09:15,912 --> 00:09:20,448 And now we'll think about the training set without that word. That's got c minus one 102 00:09:20,448 --> 00:09:24,661 words. And this one held out word over here, the blue word. And now let's do the 103 00:09:24,661 --> 00:09:28,981 same thing with a different word. Let's take out let's say the second word. So we 104 00:09:28,981 --> 00:09:33,355 still have c minus one, if we include this guy. C minus one words left in training 105 00:09:33,355 --> 00:09:37,783 and then one more word over here in the held out set. And we'll do this c times so 106 00:09:37,783 --> 00:09:43,180 each time we'll pull out one word. So we pulled out words one by one and what we've 107 00:09:43,180 --> 00:09:48,635 created is a held out set that's of size c, but each word in it was created from a 108 00:09:48,635 --> 00:09:53,958 training set that was missing that word, a training set of size c-1 minus that word. So 109 00:09:53,958 --> 00:09:59,153 imagine each of these words and their corresponding training sets. And we can 110 00:09:59,153 --> 00:10:04,911 look at a picture developed by Dan Klein to think about this intuition. And here 111 00:10:04,911 --> 00:10:09,734 we've just turned those held out and training sets on their side. So I still 112 00:10:09,734 --> 00:10:14,684 have of length C, but I've now written them vertically. And now let's, think 113 00:10:14,684 --> 00:10:19,697 about this intuition. I've got C training sets, each one of size C-1 and 114 00:10:19,697 --> 00:10:24,901 then I have a, each one has a held out set of size one. And let's try to answer the 115 00:10:24,901 --> 00:10:30,153 question, what fraction of held out words, are unseen in training. Well. These words 116 00:10:30,153 --> 00:10:35,323 N sub-zero, the words unseen in training. Each word that's unseen in 117 00:10:35,323 --> 00:10:40,021 training occurred one time in the original training set, before we removed, 118 00:10:40,021 --> 00:10:44,672 we took out each of our held out data. If there was a word that occurred once in 119 00:10:44,672 --> 00:10:49,205 training, so it's in N sub one. Occurred once in training, and we take it out of 120 00:10:49,205 --> 00:10:53,797 its training set, leaving C minus one words, then that word occurs zero times in 121 00:10:53,797 --> 00:10:58,273 its training set, the new training set without that word. So the word, the held 122 00:10:58,273 --> 00:11:02,923 out words, N subzero of them, those N subzero words, were the words that were N 123 00:11:02,923 --> 00:11:07,526 sub one in their original training set, before you removed them. So. If we wanna 124 00:11:07,526 --> 00:11:12,383 know how many words are unseen in training, it's the words that occurred 125 00:11:12,383 --> 00:11:17,472 one time in the original training set, or N one over C. Well correspondingly if we 126 00:11:17,472 --> 00:11:22,327 want to know, let me clear that up, what fraction of words are seen k times in 127 00:11:22,327 --> 00:11:27,120 training, let's pick a k, perhaps there will be two, so we pick n sub two, then 128 00:11:27,120 --> 00:11:31,722 the number of things that occur two times in our held out set is the number of 129 00:11:31,722 --> 00:11:36,383 things that occurred three times in the original training, before we removed one, 130 00:11:36,383 --> 00:11:41,102 one copy of each of those words, so now they occur only twice. So we need to think 131 00:11:41,102 --> 00:11:45,938 if we wanna know how many words occurred K times in training to estimate that, it's 132 00:11:45,938 --> 00:11:50,913 really the words that occur K+1 times in our original training set. And then 133 00:11:50,913 --> 00:11:59,552 we're gonna wanna we're gonna wanna multiply that by the number of words that 134 00:11:59,552 --> 00:12:05,234 occur, each of those words occurs in k plus one times so k plus one were 135 00:12:05,234 --> 00:12:10,985 occurrences of the N sub k plus one bin each of which has N sub k plus one words 136 00:12:10,985 --> 00:12:16,460 in it and we'll express it as a fraction out of the total words c, remember the 137 00:12:16,460 --> 00:12:22,350 total words were c. So that's the fraction of held out words seen k times in training. 138 00:12:22,350 --> 00:12:27,990 And, that means in the future, we expect K+1 times N sub K+1 over C of the words to 139 00:12:27,990 --> 00:12:33,771 be those with training count K. And since there're N sub K words with training count 140 00:12:33,771 --> 00:12:39,133 K, we wanna, this, this fraction, this probability, we wanna distribute that over 141 00:12:39,133 --> 00:12:44,495 N sub K words. So each of those N sub K words is gonna occur with 142 00:12:44,495 --> 00:12:49,509 probability K plus one times N sub K+1 over C over N sub K, because we're 143 00:12:49,509 --> 00:12:55,148 distributing it over those words. And that means that the expected count would be 144 00:12:55,148 --> 00:13:00,857 multiplied back by C again to turn from a fraction back into a count. The expected 145 00:13:00,857 --> 00:13:06,008 count of words that occur with training count K, K sub star, is K plus one 146 00:13:06,008 --> 00:13:11,858 times the ratio of N sub K plus one over N. Sub K. So one thing we talked 147 00:13:11,858 --> 00:13:17,372 about. We always compute the count n sub k from n sub k plus one, but what do we do 148 00:13:17,372 --> 00:13:22,561 for words that are in fact the largest set, the k plus the largest number? Let's 149 00:13:22,561 --> 00:13:27,684 say that the word the is in fact the word that occured most frequently in the 150 00:13:27,684 --> 00:13:33,095 corpus. We don't have a more frequent word to estimate from. So for large k, this 151 00:13:33,095 --> 00:13:39,389 Good-Turing estimator doesn't work well because there are lots of words that may 152 00:13:39,389 --> 00:13:45,607 never have occured, let's say 4,418 times, or even 3,722 times. We're going to have 153 00:13:45,607 --> 00:13:51,883 some gaps and so we'll have some zeros. So maybe the word the. And this is some other 154 00:13:51,883 --> 00:13:57,219 word, of, and there's a missing word in here, and there's missing words here. So 155 00:13:57,219 --> 00:14:02,693 we can't always using the n+1 word to do the estimation. And a simple replacement 156 00:14:02,693 --> 00:14:08,029 for that, in fact an algorithm called Simple Good-Turing, is after the counts 157 00:14:08,029 --> 00:14:13,365 get unreliable, after the first, you know, first few counts, we just replace our 158 00:14:13,365 --> 00:14:19,186 estimator with some kind of a best fit power law. So we don't actually use Good-Turing with each 159 00:14:19,186 --> 00:14:25,515 of these higher order numbers. We just use them for the lower bins. So let's look at 160 00:14:25,515 --> 00:14:30,236 the resulting Good-Turing numbers from one example. So here's numbers from, a Church 161 00:14:30,236 --> 00:14:35,164 and Gale experiment, where they used 22 million words of AP Newswire. Here's the, 162 00:14:35,707 --> 00:14:42,759 just to remind you, here's the Good-Turing equation. So the count C star is C+1 163 00:14:42,759 --> 00:14:49,189 times NC+1 over NC. So here's the original count, C. And here are all, here's the 0's 164 00:14:49,189 --> 00:14:54,544 now replaced by the Good-Turing estimator with a little extra probability mass from, 165 00:14:54,544 --> 00:14:59,638 from N sub one. Here's the 1's, The 1's all turned into.446. All the things that 166 00:14:59,638 --> 00:15:04,601 occurred with count two, now occur with count 1.26. All the things with count 167 00:15:04,601 --> 00:15:09,891 three occur with count 2.24. So each of our counts has been discounted. Each of 168 00:15:09,891 --> 00:15:16,070 these counts have been discounted to a lower number to leave some room 169 00:15:16,070 --> 00:15:21,241 for the things with zero count. And the last thing I'm gonna leave you on is 170 00:15:21,241 --> 00:15:26,481 asking you, what's the relationship between each of these counts, the original 171 00:15:26,481 --> 00:15:31,380 counts c and these counts c star. Do you notice any general relationship?