1
00:00:01,017 --> 00:00:07,058
How do we deal with bi-grams with zero
probability. The simplest idea is called

2
00:00:07,058 --> 00:00:13,028
add-one smoothing. And let's look at a
picture that gives us the intuition of

3
00:00:13,028 --> 00:00:18,085
smoothing in general from Dan Klein. So
suppose in our training data we saw denied

4
00:00:18,085 --> 00:00:23,073
the allegations, denied the reports,
denied the claims, denied the request. And

5
00:00:23,073 --> 00:00:29,000
so we've computed probabilities. There was
seven total things following denied the

6
00:00:29,000 --> 00:00:33,081
and we can get our probabilities of
everything, of each of these things. But

7
00:00:33,081 --> 00:00:38,070
we would like to say denied the effort
might occur, denied the outcome might

8
00:00:38,070 --> 00:00:46,058
occur. So we'd like to steal some
probability mass and save it for things we

9
00:00:46,058 --> 00:00:51,015
might not see later. So this is our
training data. And this is the maximum

10
00:00:51,015 --> 00:00:55,094
likelihood count, so these things occurred
after [inaudible]. These never occurred.

11
00:00:55,094 --> 00:01:00,062
We'd like to steal a little, a little
probability mask from each of these words

12
00:01:00,062 --> 00:01:05,047
and put that probability mask on to all
other possible words or some set of words,

13
00:01:05,047 --> 00:01:11,062
so that the zeros go away. And the
simplest way of doing this is called Add

14
00:01:11,062 --> 00:01:17,044
One Estimation or Leplas Smoothing. And
the idea is very simple. We pretend we saw

15
00:01:17,044 --> 00:01:23,034
each word one more time than we actually
did. We just add one to all the counts. So

16
00:01:23,034 --> 00:01:30,085
if our maximum likelihood estimate. Is the
count of the bigram divided by the count

17
00:01:30,085 --> 00:01:38,015
of the count of the unigram. Or add one
estimate is the count of the bigram plus

18
00:01:38,015 --> 00:01:44,078
one over the count of the unigram plus v
We have to add V here in the denominator,

19
00:01:44,078 --> 00:01:50,015
because we're adding one to every word
that follows word I minus one. So, our

20
00:01:50,015 --> 00:01:55,059
denominator is increased, not just by the
total count of times that something

21
00:01:55,059 --> 00:02:01,002
happened to I minus one, wasn't the
previous things that followed it, but each

22
00:02:01,002 --> 00:02:06,075
one of those got incremented by one, and
there were V of them, so we have to add V

23
00:02:06,075 --> 00:02:11,024
to the denominator. This is the add one,
estimator, probability estimator. I keep

24
00:02:11,024 --> 00:02:15,055
using the term maximum likelihood
estimate, and let's just remind you what

25
00:02:15,055 --> 00:02:19,091
that means. The maximum likelihood
estimate of some parameter of some model

26
00:02:19,091 --> 00:02:24,038
from a training set is the one that
maximizes the likelihood of the training

27
00:02:24,038 --> 00:02:28,075
set, given the model. So we have some
training set, and we're gonna, a maximum

28
00:02:28,075 --> 00:02:33,063
likelihood estimator that lets us learn a
model from a training set, is the one that

29
00:02:33,063 --> 00:02:38,046
makes that training set most likely. What
do we mean by this? Suppose the word bagel

30
00:02:38,046 --> 00:02:42,092
occurs 400 times in the corpus of a
million words. And. I ask. What's the

31
00:02:42,092 --> 00:02:48,093
probability that a random word from some
other text will be bagels? Well, the

32
00:02:48,093 --> 00:02:54,011
maximum [inaudible] estimator from our
corpus is 400 over 1,000,000, or.004. Now

33
00:02:54,011 --> 00:02:59,030
this could be a bad estimate for that
other corpus. Who knows what of the other

34
00:02:59,030 --> 00:03:04,035
corpus bagel occurs 400 times per
1,000,000 or some other probability. But

35
00:03:04,035 --> 00:03:09,074
this estimate is the one that makes it
most likely the bagel will occur 400 times

36
00:03:09,074 --> 00:03:15,025
in 1,000,000 word corpus, which is what it
did occur in our training corpus. So we're

37
00:03:15,025 --> 00:03:21,043
maximizing the likelihood of our training
data. So an add one smoothing and any kind

38
00:03:21,043 --> 00:03:26,074
of smoothing is a non-maximum likelihood
estimator, because we're changing the

39
00:03:26,074 --> 00:03:31,078
counts from what they occurred in our
training data to hope to generalize

40
00:03:31,078 --> 00:03:37,022
better. So if we go back to our Berkley
Restaurant project and we add one to all

41
00:03:37,022 --> 00:03:42,087
of our accounts, here's our La Plaz smooth
bigram count and with all those 0's that

42
00:03:42,087 --> 00:03:47,073
we had have become 1's and everything else
has one added to it. So now we can compute

43
00:03:47,073 --> 00:03:54,041
the bi-gram probabilities from those
counts and just using the Laplace add one

44
00:03:54,041 --> 00:04:01,041
smoothing equation that we saw earlier and
now we got all of our Laplace, their add

45
00:04:01,041 --> 00:04:08,025
one smooth bi-grams. So we have again the
probability of two given one that is.26

46
00:04:08,025 --> 00:04:17,016
and now all of those zeros have turned
into iii.0042, .0026 and so on. Now we can

47
00:04:17,016 --> 00:04:22,082
also take those probabilities and
reconstitute the counts as if we had seen

48
00:04:22,082 --> 00:04:28,034
things the number of times that we would
have to see to get those add one

49
00:04:28,034 --> 00:04:33,078
probabilities naturally. So we take our
probabilities and we re-estimate the

50
00:04:33,078 --> 00:04:38,016
original counts as if they were the
numbers that would have given us these

51
00:04:38,016 --> 00:04:42,020
probabilities. And we ask, what are those
reconstituted counts look like. How much

52
00:04:42,020 --> 00:04:46,093
of my, has our add one smoothing changed
our probabilities? So, here's

53
00:04:46,093 --> 00:04:54,024
reconstituted counts. So, we have I wa.
It's followed by want 327 times or Chinese

54
00:04:54,024 --> 00:05:01,021
is followed by food 8.2 times. These are
reconstituted counts. And let's compare

55
00:05:01,021 --> 00:05:09,097
them to the original counts. So, up here,
here on the top we have the original

56
00:05:09,097 --> 00:05:13,080
counts and here we have our reconstituted
counts, and I want you to notice that

57
00:05:13,080 --> 00:05:19,016
there's a huge change. So in our original
count, two followed want 608 times. In our

58
00:05:19,016 --> 00:05:27,050
smoothed counts, two follows one only 238
times. So it's, it's, almost a third sma-,

59
00:05:27,050 --> 00:05:32,083
a third the si-, th-, smaller. Three times
smaller. Or, Chinese food occurs 82 times

60
00:05:32,083 --> 00:05:42,081
in our original counts and only 8.2, in
our reconstituted counts. So, that the,

61
00:05:42,081 --> 00:05:47,037
Add One Smoothing has made massive changes
to our accounts. And sometimes changing a

62
00:05:47,037 --> 00:05:52,029
factor of ten, the original counts, in
order to steal that original probability

63
00:05:52,029 --> 00:05:56,095
mass to give to all those massive number
of zeros that had to be assigned

64
00:05:56,095 --> 00:06:02,047
probabilities. In other words add one
estimation is a very blunt instrument.

65
00:06:02,047 --> 00:06:07,061
It's, it makes very big changes in the
counts in order to get these probability

66
00:06:07,061 --> 00:06:12,096
mast to assign to this massive number of
0's. And so in practice we don't actually

67
00:06:12,096 --> 00:06:17,084
use add-one smoothing for n grams. We have
better methods. We do use add-one

68
00:06:17,084 --> 00:06:22,079
smoothings for other kinds of natural
language processing models. So add-one

69
00:06:22,079 --> 00:06:27,074
smoothing for example is used in text
classification or in similar kinds of

70
00:06:27,074 --> 00:06:30,093
domain where the number of 0's isn't so
enormous.