1
00:00:02,511 --> 00:00:07,925
One sub-class networks is the class called
naive bayes or sometimes even more

2
00:00:07,925 --> 00:00:14,062
derogatory idiot bayes. As we will see naive bayes models are called
that way because they make independence

3
00:00:14,062 --> 00:00:19,415
assumptions that indeed are very naive and
overly simplistic and yet they provide an

4
00:00:19,465 --> 00:00:26,303
interesting point on the trade off curve,
of model complexity that sometimes turns

5
00:00:26,303 --> 00:00:33,248
out to be surprisingly useful. So here is
a naive bayes model. This model is typically

6
00:00:33,248 --> 00:00:38,540
used for classification, that is taking an
instance where we have effectively

7
00:00:38,540 --> 00:00:45,403
observed a bunch of features and in most
cases although not necessarily. We're

8
00:00:45,403 --> 00:00:49,536
assuming that all of these features are
observed for each of the, for a given

9
00:00:49,536 --> 00:00:56,847
instance, and out goal is to infer to
which class among the limited set of

10
00:00:56,847 --> 00:01:02,403
classes a particular instance belongs. So
these are observed, these ones here

11
00:01:02,418 --> 00:01:11,301
observed. And this one in general is
hidden. Now if you look at the assumptions

12
00:01:11,301 --> 00:01:17,653
made by this model, this model makes the
assumption that every pair of features

13
00:01:17,653 --> 00:01:35,952
xi and xj are conditionaly independent
given the class. So every xi and xj give

14
00:01:35,952 --> 00:01:42,621
us no information. One gives no
information about the other once the class

15
00:01:42,621 --> 00:01:48,094
variable is observed. Which reduces this
whole model into one where we only have to

16
00:01:48,094 --> 00:01:54,423
encode individual pair wise
interactions between the class variable

17
00:01:54,423 --> 00:02:00,873
and single features. So if we look at the
chain rule for bayesian networks as applied

18
00:02:00,873 --> 00:02:08,527
in this context, we see that we have a
joint distribution P of C comma x1 up to xn which can

19
00:02:08,527 --> 00:02:16,053
be written using a product form as a prior
over the class variable C and a product of

20
00:02:16,053 --> 00:02:24,907
the conditional probabilities of each
feature given the class. To understand this

21
00:02:24,907 --> 00:02:31,315
model a little bit better it helps also to
look at the ratio between the

22
00:02:31,315 --> 00:02:35,414
probabilities of two different classes
given the particular observation that is a

23
00:02:35,414 --> 00:02:42,436
particular assignment x1 up to xn to
the observed features So if we look at this

24
00:02:42,436 --> 00:02:47,669
ratio, we can see that it can be broken
down as a product of two terms. The first

25
00:02:47,669 --> 00:02:53,665
is just the ratio of the prior
probabilities of the two classes. So

26
00:02:53,665 --> 00:02:58,336
that's the green term here. And the second
is this blue term, which is a product of

27
00:02:58,336 --> 00:03:07,296
odd ratios, as it's called. That is the
probability of seeing a particular

28
00:03:07,296 --> 00:03:14,804
observation xi In the context of
one class, relative to the context of the

29
00:03:14,804 --> 00:03:23,384
other class So let's look at an
application of the naive bayes in one of

30
00:03:23,384 --> 00:03:25,577
the places where it is actually very
commonly used which is the context of

31
00:03:25,577 --> 00:03:33,725
text classification. So imagine that we're
trying to pick a document and figure out

32
00:03:33,725 --> 00:03:40,966
for that document to which category
it belonged we have some set of categories

33
00:03:40,966 --> 00:03:43,390
in mind so for example is this a document
about pets, is it about finance, is it

34
00:03:43,390 --> 00:03:46,390
about vacations? We have some set of
categories and we like to assign a

35
00:03:46,390 --> 00:03:52,143
document to one of those. It turns out
that one can use two different naive

36
00:03:52,143 --> 00:03:57,663
bayes models for tackling this problem.
The first of those is called the

37
00:03:57,663 --> 00:04:06,191
bernouli naive bayes model for text, and it,
it treats every word in a dictionary so you

38
00:04:06,191 --> 00:04:08,585
open your dictionary and there is several,
maybe ten thousand words in that

39
00:04:08,585 --> 00:04:13,665
dictionary and so you have a random
variable for every one of those words, or

40
00:04:13,665 --> 00:04:16,460
at least the ones that occur the kind of
document that your interested in thinking

41
00:04:16,460 --> 00:04:22,629
about. And for each word in the dictionary
we have a binary random variable which is

42
00:04:22,629 --> 00:04:42,167
one If the word appears in the document
and zero otherwise If we have say 5000

43
00:04:42,167 --> 00:04:47,207
words that we're interested in reasoning about
we would have 5000 of these binary variables. And

44
00:04:47,207 --> 00:04:51,271
so the probability associated, the
CPD associated with each variable

45
00:04:51,271 --> 00:04:56,559
is in this case the probability that the
word appears say the probability that the

46
00:04:56,559 --> 00:05:01,711
cat, the word cat appears given the label
of the document. So for example if we had

47
00:05:01,711 --> 00:05:06,718
two categories that were looking at right
now, say documents about finances vs

48
00:05:06,718 --> 00:05:11,845
documents about, document about pets. You
would expect that in a document about pets

49
00:05:11,845 --> 00:05:18,601
the word cat is quite likely to appear and
so I'm only showing the probability of cat

50
00:05:18,601 --> 00:05:23,611
appearing, the probability of cat not
appearing will be 0.7, the probability

51
00:05:23,611 --> 00:05:29,988
that dog appears might be 0.4 and, and so
on. Whereas for documents about finances

52
00:05:29,988 --> 00:05:36,331
we're much less likely to see the word
cat. Dog a little bit more likely to have

53
00:05:36,331 --> 00:05:41,470
the words buy and sell, so the probability
that by appears might be considerably

54
00:05:41,470 --> 00:05:49,622
higher in this case. So this is a bernouli naive bayes
model because first, it the bernouli

55
00:05:49,622 --> 00:05:55,674
model because each of these is a binary
variable with subject to a bernouli

56
00:05:55,674 --> 00:05:58,707
distribution. So this is Bernouli
distribution. And it's naive Bayes because it makes

57
00:05:58,707 --> 00:06:04,668
very strong independence assumptions that
the probability of one word appearing is

58
00:06:04,668 --> 00:06:10,359
independent of sorry the event of one word
appearing is independent of the event of a

59
00:06:10,359 --> 00:06:13,448
different word appearing given that we
know the class and obviously that assumption

60
00:06:13,448 --> 00:06:18,828
is Far too strong to be represented as a
reality, but it turns out to be a not bad

61
00:06:18,828 --> 00:06:26,327
approximation in terms of actual
performance. A second model for the

62
00:06:26,327 --> 00:06:32,146
same problem is what's called the
multinomial naive Bayes model for text. In this

63
00:06:32,146 --> 00:06:37,236
case the variables that represent the
features are not the words in the

64
00:06:37,236 --> 00:06:42,517
dictionary, but rather words in the
documents. So here n is the

65
00:06:42,517 --> 00:06:51,720
length of the document. So if you have a
document that has 737 words, your gonna

66
00:06:51,720 --> 00:06:58,186
have 737 random variables, and the value
of each of these random variables is the

67
00:06:58,186 --> 00:07:06,128
actual word. That is in the first, second, up to the n'th position in the

68
00:07:06,128 --> 00:07:12,838
document. And so the, if we have say that
same dictionary of 5000 possible words

69
00:07:12,838 --> 00:07:19,851
this is no longer binary random variable
but rather one that has D values where

70
00:07:19,851 --> 00:07:27,993
this is the size of the dictionary.
Say 5000 Now this might seem like

71
00:07:27,993 --> 00:07:34,581
a very complicated model because, the
CPD now needs to specify the

72
00:07:34,581 --> 00:07:40,672
probability distribution over words in the
dictionary for every possible word. For every

73
00:07:40,672 --> 00:07:47,499
possible position in the documents so we
need to have a probability distribution

74
00:07:47,499 --> 00:07:50,563
over the words in position one, in
position two, and in position n, but we're

75
00:07:50,563 --> 00:07:55,958
going to address that by assuming that
these probability distributions are all

76
00:07:55,958 --> 00:08:02,864
the same and so the probability
distribution for, over words in position

77
00:08:02,864 --> 00:08:09,425
one is the same as for words in positions
two, three, and so on Now this is a

78
00:08:09,425 --> 00:08:15,019
Multinomial naive Bayes model because notice
that the parametrisation for each of these

79
00:08:15,019 --> 00:08:19,556
words is a multinomial distribution
so what we see here is not the same as

80
00:08:19,556 --> 00:08:25,595
what we saw in the previous slide, but he
had a bunch of binary random variables,

81
00:08:25,595 --> 00:08:30,688
here this is a multi nomial Which
means that all of these entries sum to one

82
00:08:30,688 --> 00:08:41,259
and it's a naive naive bayes model because
it makes, again, a strong independence

83
00:08:41,259 --> 00:08:43,002
assumption. A different independence
assumption. In this case it makes the

84
00:08:43,002 --> 00:08:47,866
assumption that the word in position one
is independent of the word in position two

85
00:08:47,866 --> 00:08:53,263
given the class variable. And once again,
if you think about, say, two-word phrases

86
00:08:53,263 --> 00:08:59,340
that are common, this assumption is
clearly overly strong and yet it appears

87
00:08:59,340 --> 00:09:06,729
to be a good approximation. In a variety
of practical applications and most notably

88
00:09:06,729 --> 00:09:11,862
in the case of natur-, of this kind of
document classification where it's still

89
00:09:11,862 --> 00:09:16,167
quite commonly used. So to summarize,
naive bayes actually provides us with a

90
00:09:16,167 --> 00:09:20,389
very simple approach for classification
problems. It's computationally very

91
00:09:20,389 --> 00:09:25,823
efficient and the models are easy to
construct, whether by hand or by machine

92
00:09:25,823 --> 00:09:31,662
learning techniques. It turns out to be a
surprisingly effective method in domains

93
00:09:31,662 --> 00:09:34,907
that have a large number of weekly
relevant features, such as the text

94
00:09:34,907 --> 00:09:39,412
domains that we talked about. On the other
hand, the strong independence assumptions

95
00:09:39,412 --> 00:09:42,732
that we talked about, the conditional
independence of different features given

96
00:09:42,732 --> 00:09:47,985
the class, reduce the performance of these
models, especially in cases where we have

97
00:09:47,985 --> 00:09:50,624
multiple, highly correlated features.