1
00:00:09,070 --> 00:00:12,820
In this video we are going to talk about one of

2
00:00:12,820 --> 00:00:17,750
the classification algorithms called the Naïve Bayes classifier.

3
00:00:17,750 --> 00:00:22,345
Let's take a case to set up the scenario.

4
00:00:22,345 --> 00:00:28,495
This is the task of classifying text search queries.

5
00:00:28,495 --> 00:00:33,165
So suppose you are interested in classifying search queries and you have three classes.

6
00:00:33,165 --> 00:00:37,105
The Entertainment class, the Computer Science class,

7
00:00:37,105 --> 00:00:39,015
and the Zoology class.

8
00:00:39,015 --> 00:00:43,750
The three subjects. And then you

9
00:00:43,750 --> 00:00:49,320
know that most of these search queries are about Entertainment.

10
00:00:49,320 --> 00:00:51,610
So that's what you know coming in.

11
00:00:51,610 --> 00:00:53,515
That if you don't know anything else,

12
00:00:53,515 --> 00:00:59,070
the chances that it's an entertainment related query is pretty high.

13
00:00:59,070 --> 00:01:02,105
Then you get the query.

14
00:01:02,105 --> 00:01:05,320
And the query is "Python".

15
00:01:05,320 --> 00:01:09,015
And the task is still the same.

16
00:01:09,015 --> 00:01:12,500
The task is, can you classify Python as entertainment,

17
00:01:12,500 --> 00:01:16,170
computer science, or zoology?

18
00:01:16,170 --> 00:01:19,320
Is it Python the snake?

19
00:01:19,320 --> 00:01:22,740
If that is the case then it is a zoology document.

20
00:01:22,740 --> 00:01:25,660
But what it is actually Python the programming

21
00:01:25,660 --> 00:01:30,235
language like apply data mining in Python, right?

22
00:01:30,235 --> 00:01:34,475
Then it belongs to computer science.

23
00:01:34,475 --> 00:01:39,250
But if it is Python as in Monty Python then it is entertainment.

24
00:01:39,250 --> 00:01:45,120
So just the word "Python" could still mean one of these three.

25
00:01:45,120 --> 00:01:49,655
But then you think that Python as itself,

26
00:01:49,655 --> 00:01:54,230
the most common class becomes zoology.

27
00:01:54,230 --> 00:01:59,390
So even though generally the queries are entertainment queries,

28
00:01:59,390 --> 00:02:03,050
when you see the word "Python" and if that is your query then

29
00:02:03,050 --> 00:02:07,780
the chances that it is actually zoology becomes higher.

30
00:02:07,780 --> 00:02:13,470
Then you have another word and this time is "Python download".

31
00:02:13,470 --> 00:02:19,460
And then you can say that the most probably class is in fact computer science.

32
00:02:19,460 --> 00:02:21,990
So what just happened there?

33
00:02:21,990 --> 00:02:24,965
You had a model,

34
00:02:24,965 --> 00:02:28,790
in this case a probabilistic model that tells

35
00:02:28,790 --> 00:02:34,150
you the likelihood of a class before you have any information.

36
00:02:34,150 --> 00:02:36,780
And then when you are given new information,

37
00:02:36,780 --> 00:02:40,055
you updated that likelihood of the class.

38
00:02:40,055 --> 00:02:46,980
So you had a model that said "Entertainment is typically what any standard query,

39
00:02:46,980 --> 00:02:49,135
typical query, would be".

40
00:02:49,135 --> 00:02:53,640
But then given the new information about the word "Python" you said "Oh,

41
00:02:53,640 --> 00:02:56,865
the likelihood of it being zoology is higher".

42
00:02:56,865 --> 00:03:00,800
And it's not likely to be entertainment anymore.

43
00:03:00,800 --> 00:03:03,395
Even though there are cases of Python,

44
00:03:03,395 --> 00:03:07,590
as in Monty Python, where it would be entertainment.

45
00:03:07,590 --> 00:03:14,040
So this change is what is in the crux of this Naïve Bayes classifier.

46
00:03:14,040 --> 00:03:19,320
You have something called prior probability that is the prior knowledge or

47
00:03:19,320 --> 00:03:26,385
the prior belief that the label belongs to entertainment,

48
00:03:26,385 --> 00:03:28,725
Or the label it's computer science,

49
00:03:28,725 --> 00:03:30,335
or the label is zoology.

50
00:03:30,335 --> 00:03:33,135
This is one of the three options you have.

51
00:03:33,135 --> 00:03:37,155
So you have a prior probability for each of them.

52
00:03:37,155 --> 00:03:42,335
And by basic probability you know that these are the only three options.

53
00:03:42,335 --> 00:03:44,985
So the sum of these two probabilities should be one.

54
00:03:44,985 --> 00:03:46,665
It's definitely one of the three.

55
00:03:46,665 --> 00:03:50,015
It's either entertainment, or computer science, or zoology.

56
00:03:50,015 --> 00:03:53,525
But among the three entertainment is more likely.

57
00:03:53,525 --> 00:04:01,410
And then when you have new information like the x is Python and input is Python,

58
00:04:01,410 --> 00:04:06,630
so when you have new information your probability and likelihood changes.

59
00:04:06,630 --> 00:04:13,780
Your probability of entertainment given the input is Python is suddenly lower.

60
00:04:13,780 --> 00:04:20,260
And the probability of y being computer science given x is Python is higher.

61
00:04:20,260 --> 00:04:23,990
And probability of y given zoology is even higher.

62
00:04:23,990 --> 00:04:26,690
That's why you would say that "Given the input Python,

63
00:04:26,690 --> 00:04:29,600
the label is zoology".

64
00:04:29,600 --> 00:04:33,920
So this is encapsulated in what is called Baye's Rule or Based

65
00:04:33,920 --> 00:04:39,815
theorem and that says that "The posterior probability depends on your prior.

66
00:04:39,815 --> 00:04:45,865
But then also depends on the likelihood of that happening or that event happening".

67
00:04:45,865 --> 00:04:47,470
And divided by the evidence.

68
00:04:47,470 --> 00:04:51,520
So in mathematical terms it comes to probability of y given

69
00:04:51,520 --> 00:04:57,160
X is probability of Y which is the prior probability.

70
00:04:57,160 --> 00:05:05,200
And probability of X given y which is the likelihood of having the data as X given y.

71
00:05:05,200 --> 00:05:09,115
That means, if you know that the label is zoology,

72
00:05:09,115 --> 00:05:16,335
the probability of seeing Python is so in zoology documents let's say.

73
00:05:16,335 --> 00:05:20,230
Or if you know that the label is entertainment the,

74
00:05:20,230 --> 00:05:25,705
the probability of seeing Python in entertainment is so and so and that is lower.

75
00:05:25,705 --> 00:05:28,330
That's significantly lower than the other one.

76
00:05:28,330 --> 00:05:33,505
Then if the class was zoology.

77
00:05:33,505 --> 00:05:38,855
So the Naïve Bayes classifier looks at this computation,

78
00:05:38,855 --> 00:05:41,480
looks at what is the probability of

79
00:05:41,480 --> 00:05:45,930
a class like computer science given the input as Python.

80
00:05:45,930 --> 00:05:50,955
And if computes is saying "What is the chance that it was coming to science in general?

81
00:05:50,955 --> 00:05:55,345
What is the likelihood of it being computer science or the prior probability?

82
00:05:55,345 --> 00:05:57,570
And then what is the likelihood of seeing the word

83
00:05:57,570 --> 00:06:00,960
Python in documents that are computer science.

84
00:06:00,960 --> 00:06:03,740
The same thing with zoology.

85
00:06:03,740 --> 00:06:08,980
So the probability of the class being zoology given Python is,

86
00:06:08,980 --> 00:06:14,000
what is a prior probability of the class being zoology without knowing any information?

87
00:06:14,000 --> 00:06:18,700
And then given that it is the zoology class document,

88
00:06:18,700 --> 00:06:20,560
what is the chance that you will see?

89
00:06:20,560 --> 00:06:23,045
What is the likelihood of seeing Python?

90
00:06:23,045 --> 00:06:26,571
And then you will say that if probability of y as CS

91
00:06:26,571 --> 00:06:31,315
given Python is higher than y as zoology,

92
00:06:31,315 --> 00:06:39,505
the label as zoology given Python then I'm going to call the label as computer science.

93
00:06:39,505 --> 00:06:45,875
So in general, you're saying that probability of y given X is computed this way.

94
00:06:45,875 --> 00:06:50,350
But then the Naïve Bayes classification model just

95
00:06:50,350 --> 00:06:55,920
is interested in which of the three labels is more likely.

96
00:06:55,920 --> 00:06:58,330
So you know that y belongs to one of the three classes.

97
00:06:58,330 --> 00:07:02,000
Entertainment, conputer science, or zoology.

98
00:07:02,000 --> 00:07:05,935
It's only important to know which among those three is higher.

99
00:07:05,935 --> 00:07:08,175
And so, the true label,

100
00:07:08,175 --> 00:07:10,220
or the predicted label I should say,

101
00:07:10,220 --> 00:07:17,590
y* is the y that maximizes probabilit of y given X.

102
00:07:17,590 --> 00:07:23,990
And then that computation it does not matter what the probability of X itself is.

103
00:07:23,990 --> 00:07:28,080
So what is the probability of seeing a query like Python.

104
00:07:28,080 --> 00:07:31,640
And you can remove it then because it does not matter,

105
00:07:31,640 --> 00:07:35,440
it doesn't change with the label assigned to it.

106
00:07:35,440 --> 00:07:40,155
This in addition to what is called the Naïve assumption

107
00:07:40,155 --> 00:07:45,655
of Bayesian classification forms the Naïve Bayes classifier.

108
00:07:45,655 --> 00:07:49,155
And the Naïve assumption is that given the class label,

109
00:07:49,155 --> 00:07:53,175
the features themselves are independent of each other.

110
00:07:53,175 --> 00:07:58,050
That is given the label is y,

111
00:07:58,050 --> 00:08:04,665
probability of capital X given y is just individual feature probabilities.

112
00:08:04,665 --> 00:08:09,255
Probability of x_i given a product of all of those.

113
00:08:09,255 --> 00:08:14,035
That's the product that goes from the first feature to the end feature.

114
00:08:14,035 --> 00:08:20,020
This is the final formulation of a Naïve Bayes classifier.

115
00:08:20,020 --> 00:08:23,930
So the formula stands like this.

116
00:08:23,930 --> 00:08:29,420
The predicted label y is the y that maximizes,

117
00:08:29,420 --> 00:08:35,525
the argument that maximizes this computation of probability of y given X.

118
00:08:35,525 --> 00:08:40,460
Which is computed using Bayes Rule as probability of y, that is the prior,

119
00:08:40,460 --> 00:08:47,045
times T independent products of individual features given y.

120
00:08:47,045 --> 00:08:52,955
So that's the likelihood of probatility of capital X given y.

121
00:08:52,955 --> 00:08:56,990
So for example, if the query is Python download,

122
00:08:56,990 --> 00:09:05,520
you're going to say "The predicted y is the y that maximizes probability of y.

123
00:09:05,520 --> 00:09:07,980
Probability of Python given y,

124
00:09:07,980 --> 00:09:10,580
and probability of download given y.

125
00:09:10,580 --> 00:09:13,445
So for example, if it is zoology,

126
00:09:13,445 --> 00:09:18,295
you know that probability of zoology is low.

127
00:09:18,295 --> 00:09:22,505
People don't typically ask zoology queries.

128
00:09:22,505 --> 00:09:27,025
But then probability of Python given zoology is very high.

129
00:09:27,025 --> 00:09:32,140
However, probability of download given Python is very low.

130
00:09:32,140 --> 00:09:35,270
However, in the case of computer science,

131
00:09:35,270 --> 00:09:39,010
probability of computer science queries in general is somewhere in the middle.

132
00:09:39,010 --> 00:09:45,640
Probability of Python given computer sciences not up there but also significant.

133
00:09:45,640 --> 00:09:49,735
Whereas probability of download given computer science is very significant.

134
00:09:49,735 --> 00:09:54,470
And a product of all of the three makes computer science as

135
00:09:54,470 --> 00:09:59,670
to be the best predicted leap.

136
00:09:59,670 --> 00:10:02,650
So in Naïve Bayes we saw the model is

137
00:10:02,650 --> 00:10:06,430
just individual probabilities that you multiply together.

138
00:10:06,430 --> 00:10:08,920
So what are the parameters there?

139
00:10:08,920 --> 00:10:10,845
We have the prior probabilities.

140
00:10:10,845 --> 00:10:12,760
The prior probabilities are

141
00:10:12,760 --> 00:10:17,840
these probabilities for each of the classes in your set of classes.

142
00:10:17,840 --> 00:10:22,545
So that's probability of y for all y in capital Y.

143
00:10:22,545 --> 00:10:25,070
And then you have the likelihoods.

144
00:10:25,070 --> 00:10:31,790
And that this probability of seeing a particular feature in documents of class y.

145
00:10:31,790 --> 00:10:36,061
The probability of x_i given y that is import, no,

146
00:10:36,061 --> 00:10:42,400
that is needed for all features x_i and all labels y in Y.

147
00:10:42,400 --> 00:10:50,690
So it's a combination of every feature in each of these classes that you have.

148
00:10:50,690 --> 00:10:52,540
So let's take an exercise.

149
00:10:52,540 --> 00:10:56,330
If you have three classes that is capital Y is three.

150
00:10:56,330 --> 00:11:00,335
And you have hundred features in your X,

151
00:11:00,335 --> 00:11:02,170
that means X goes from X1,

152
00:11:02,170 --> 00:11:05,535
X2 up to X100.

153
00:11:05,535 --> 00:11:13,340
Can you compare how many parameters are there in the Naïve Bayes model? Give it a try.

154
00:11:14,780 --> 00:11:21,180
No? Once you know what are the parameters that you learned in a Naïve Bayes model,

155
00:11:21,180 --> 00:11:24,450
let's see how do you actually learned it.

156
00:11:24,450 --> 00:11:31,480
So you have prior probabilities like probability of y for all Y in the set of labels.

157
00:11:31,480 --> 00:11:33,340
How do you identify that?

158
00:11:33,340 --> 00:11:42,775
How do you know that the most common class of search queries is entertainment?

159
00:11:42,775 --> 00:11:46,850
Well, you have the training data.

160
00:11:46,850 --> 00:11:49,935
So you have the set of documents are

161
00:11:49,935 --> 00:11:54,730
all the queries that are labeled as which class they belong to.

162
00:11:54,730 --> 00:11:58,275
So you have a query such as

163
00:11:58,275 --> 00:12:03,635
Ashton Kutcher and that query would be entertainment, or Lady Gaga.

164
00:12:03,635 --> 00:12:05,325
That is also entertainment.

165
00:12:05,325 --> 00:12:07,505
Or tiger.

166
00:12:07,505 --> 00:12:14,130
And in the context of zoology as an animal and that would be zoology.

167
00:12:14,130 --> 00:12:21,365
Or something like C++ and that is computer science and so on.

168
00:12:21,365 --> 00:12:24,660
So you can just count the number of instances

169
00:12:24,660 --> 00:12:27,660
you have in your training data in each of these classes.

170
00:12:27,660 --> 00:12:29,160
In the example I gave,

171
00:12:29,160 --> 00:12:36,260
I gave you two examples of entertainment and one each of computer science and zoology.

172
00:12:36,260 --> 00:12:41,625
So your class distribution just with four instances would be half for entertainment,

173
00:12:41,625 --> 00:12:43,980
one quarter for zoology,

174
00:12:43,980 --> 00:12:45,825
and one quarter for computer science.

175
00:12:45,825 --> 00:12:51,630
In general, if there are any instances and small enough those are belonging to

176
00:12:51,630 --> 00:12:59,675
a particular class y then your probability of class y is small and or capital N.

177
00:12:59,675 --> 00:13:04,525
The next set of parameters you have is likelihood.

178
00:13:04,525 --> 00:13:08,630
So recall that likelihood is probably of x_i given

179
00:13:08,630 --> 00:13:13,675
Y for all features x_i and for all labels y.

180
00:13:13,675 --> 00:13:17,070
So it's a combination of the many, many features here.

181
00:13:17,070 --> 00:13:18,410
So how do you count those?

182
00:13:18,410 --> 00:13:22,790
So the way you do that would be you count the number of times

183
00:13:22,790 --> 00:13:27,970
feature x_i appears in instances labeled as class y.

184
00:13:27,970 --> 00:13:31,610
So you only focus on the instances that were labeled

185
00:13:31,610 --> 00:13:38,060
class y and among those see how many times the feature x_i occurs.

186
00:13:38,060 --> 00:13:43,175
So for example, you will only look at documents that belong to

187
00:13:43,175 --> 00:13:52,026
the computer science class and among those you would count how many times Python appears.

188
00:13:52,026 --> 00:13:56,420
OK? Or you would look at all the queries that we will call

189
00:13:56,420 --> 00:13:59,360
entertainment and then look for word like

190
00:13:59,360 --> 00:14:03,945
"actor" and see how many times the word "actor" occurs in those queries.

191
00:14:03,945 --> 00:14:09,840
So that would be probability of word "actor" given the class entertainment.

192
00:14:09,840 --> 00:14:13,380
So there are p instances of class y and x_i

193
00:14:13,380 --> 00:14:17,760
the feature x_i appears in k of them then the probability of x_i and

194
00:14:17,760 --> 00:14:26,745
y would be k / p. When you do this counting there is a slight problem.

195
00:14:26,745 --> 00:14:29,090
And that problem is,

196
00:14:29,090 --> 00:14:34,175
what happens if the probability becomes zero? So for example.

197
00:14:34,175 --> 00:14:42,055
If you have never seen the word "actor" in queries that were labeled entertainment.

198
00:14:42,055 --> 00:14:46,115
Or let's say you never saw the word "python"

199
00:14:46,115 --> 00:14:50,240
in the queries that were labeled entertainment.

200
00:14:50,240 --> 00:14:54,755
Because for some reason in your dataset you never saw Monty Python.

201
00:14:54,755 --> 00:14:59,345
Then the probability the way you compute it would be zero.

202
00:14:59,345 --> 00:15:03,620
But that is a problem because if you have the probability to

203
00:15:03,620 --> 00:15:07,805
be zero and it is multiplied to all the other probabilities,

204
00:15:07,805 --> 00:15:12,175
the overall probability will end up being zero.

205
00:15:12,175 --> 00:15:16,530
So when a feature x_i never occurs documents labelled y,

206
00:15:16,530 --> 00:15:21,015
it can never be the case that whenever you see the word,

207
00:15:21,015 --> 00:15:24,155
the feature x_i that the label is y.

208
00:15:24,155 --> 00:15:27,040
You don't want to be that strict.

209
00:15:27,040 --> 00:15:29,330
So you don't want to say that

210
00:15:29,330 --> 00:15:34,610
the posterior probability of y given x_i will be zero because that

211
00:15:34,610 --> 00:15:38,390
would make any document that has Python to

212
00:15:38,390 --> 00:15:42,895
never be called an entertainmenet class, right?

213
00:15:42,895 --> 00:15:45,710
So what you would want to do instead is to smooth

214
00:15:45,710 --> 00:15:48,950
the parameters and then you smooth the parameters.

215
00:15:48,950 --> 00:15:53,270
One of the options to do it would be just add a dummy count.

216
00:15:53,270 --> 00:15:57,740
You say, it's never the case that the count to zero.

217
00:15:57,740 --> 00:16:04,490
So I add count of one to every word in every class.

218
00:16:04,490 --> 00:16:07,680
This does not change the order probability significantly

219
00:16:07,680 --> 00:16:11,460
because that's the way we are computed these probabilities.

220
00:16:11,460 --> 00:16:15,090
These are called "maximum likelihood estimations" that typically good

221
00:16:15,090 --> 00:16:18,925
when you have large numbers but they're not so good when you have very small numbers.

222
00:16:18,925 --> 00:16:21,435
So by adding count of one,

223
00:16:21,435 --> 00:16:25,365
you don't really significantly change the larger numbers there.

224
00:16:25,365 --> 00:16:27,735
Because what you do now is you say,

225
00:16:27,735 --> 00:16:31,860
probability of X_i given y instead of k / p,

226
00:16:31,860 --> 00:16:35,355
you're going to say "I'm going to add one to every word".

227
00:16:35,355 --> 00:16:43,055
So it's going to be k + 1 over p plus n because in all I have added n words as dummies.

228
00:16:43,055 --> 00:16:48,345
So that would be your way by which now you'll never have a probability of zero here.

229
00:16:48,345 --> 00:16:52,065
Because if k indeed was zero,

230
00:16:52,065 --> 00:16:57,720
the probability would still be one over p + n. So this way,

231
00:16:57,720 --> 00:17:01,365
how can I've awarded this problem of zero counts?

232
00:17:01,365 --> 00:17:04,650
Now, you might imagine and wonder if you would

233
00:17:04,650 --> 00:17:09,630
want to do something similar to the prior probabilities.

234
00:17:09,630 --> 00:17:13,850
Think about it and we'll talk about it in one of the queries.

235
00:17:13,850 --> 00:17:16,600
The immediate questions soon.

236
00:17:16,600 --> 00:17:18,885
So to bring it all together.

237
00:17:18,885 --> 00:17:24,945
The big take home messages from this video is that Naive Bayes is

238
00:17:24,945 --> 00:17:28,530
a probabilistic model and it is called Naive because it assumes

239
00:17:28,530 --> 00:17:33,195
that features are independent of each other given the class label.

240
00:17:33,195 --> 00:17:39,390
It is Naive because it's actually not necessarily true even for text.

241
00:17:39,390 --> 00:17:42,930
So for example, the fact that you have "White House" as

242
00:17:42,930 --> 00:17:47,550
two words but together having a significantly different meaning.

243
00:17:47,550 --> 00:17:50,835
If you see the word "White" with a capital W,

244
00:17:50,835 --> 00:17:56,430
the chance that it is followed by "House" is very high.

245
00:17:56,430 --> 00:18:02,105
So these two features of "White" and "House" are not really independent of each other.

246
00:18:02,105 --> 00:18:06,280
But Naïve Bayes models kind of ignored that.

247
00:18:06,280 --> 00:18:09,030
They say that given the class label,

248
00:18:09,030 --> 00:18:12,810
I'm assuming all features are independent because the math

249
00:18:12,810 --> 00:18:18,025
on how you can compute the probabilities becomes easy.

250
00:18:18,025 --> 00:18:22,800
Even so, for text classification problems,

251
00:18:22,800 --> 00:18:26,690
Naïve Bayes models actually typically provide very strong baselines.

252
00:18:26,690 --> 00:18:29,935
It is traditionally the first one you should try because.

253
00:18:29,935 --> 00:18:33,755
It will give you the benchmark or a baseline that is pretty strong.

254
00:18:33,755 --> 00:18:37,200
And then you can look at other models that you see

255
00:18:37,200 --> 00:18:43,380
soon for how well it improves over Naïve Bayes models.

256
00:18:43,380 --> 00:18:46,015
It's a very simple model to learn.

257
00:18:46,015 --> 00:18:50,940
The parameters are very easy to understand and to learn because they are just counts.

258
00:18:50,940 --> 00:18:54,500
Ad they are just counts counted in different ways and so on.

259
00:18:54,500 --> 00:18:57,410
So the big message is Naïve Bayes is

260
00:18:57,410 --> 00:18:59,640
a very important classifier

261
00:18:59,640 --> 00:19:03,640
for text classification and should be the first one you should try.