1
00:00:02,820 --> 00:00:06,546
So as we said at the very beginning,
there's two main families of graphical

2
00:00:06,546 --> 00:00:10,174
models. There's those that are based on
directed graphs, directed acyclic

3
00:00:10,174 --> 00:00:13,553
graphs, and those that are based on
undirected graphs. The undirected

4
00:00:13,553 --> 00:00:17,180
graphical models are typically called
Markov networks. They're also called

5
00:00:17,180 --> 00:00:21,404
Markov random fields. We're going to start
by talking about the simplest sub class of

6
00:00:21,404 --> 00:00:25,130
those, which is pairwise Markov
networks, and then we're gonna generalize

7
00:00:25,130 --> 00:00:29,841
it. So let's look again at a toy example
just to illustrate what's going on. This

8
00:00:29,841 --> 00:00:34,581
is an example of four people who are
studying together in study pairs. And

9
00:00:34,581 --> 00:00:39,498
notice that Alice and Charles don't get
along. And, you know, Bob and Debbie had a

10
00:00:39,498 --> 00:00:44,356
bad breakup so they don't talk to each
other either. And so really we only have

11
00:00:44,356 --> 00:00:48,798
the study pairs that are marked by the
edges on this diagram. The random

12
00:00:48,798 --> 00:00:54,596
variables here indicate whether the
students have a particular misconception

13
00:00:54,596 --> 00:01:00,470
because the material was a little confusing. So the
random variable says does the student

14
00:01:00,470 --> 00:01:06,118
have a misconception or not, this
particular misconception. The intuition

15
00:01:06,118 --> 00:01:12,217
here says if two students study together
then they kind of influence each other. So we

16
00:01:12,217 --> 00:01:18,235
have for example if Alice and Bob study
together then this edge indicates that if

17
00:01:18,235 --> 00:01:22,245
one of them has the misconception, the
other one is likely to have the

18
00:01:22,245 --> 00:01:26,421
misconception. Now, this doesn't fit
neatly into the purview of the directed

19
00:01:26,421 --> 00:01:30,821
graph, because the influence flows in both
directions. You can't really point an

20
00:01:30,821 --> 00:01:35,053
arrow from Alice to Bob or from Bob to
Alice. So we're going to use an undirected

21
00:01:35,053 --> 00:01:39,805
graph to represent this. So that's great,
but how do you parametrize an undirected

22
00:01:39,805 --> 00:01:44,179
graph? Because you no longer have the
notion of a conditional probability

23
00:01:44,179 --> 00:01:48,853
distribution, because there's no variable
that's conditioning and one that you

24
00:01:48,853 --> 00:01:53,886
condition on. And so, and so, how do we do
this? And we're, so we're going to use the

25
00:01:53,886 --> 00:01:58,440
general notion of a factor, which we
defined previously. And notice that this

26
00:01:58,440 --> 00:02:03,293
really is a general factor, in that the
numbers don't even, are not even within

27
00:02:03,293 --> 00:02:08,227
the range [0, 1]. Now, what do these factors
mean? These factors have many names;

28
00:02:08,227 --> 00:02:15,874
they're called affinity functions or
compatibility functions. They're also,

29
00:02:15,874 --> 00:02:26,369
they're also called soft constraints in
different settings. So what these numbers

30
00:02:26,369 --> 00:02:33,257
mean is the oh, is the local happiness of
the variables A and B to take a particular

31
00:02:33,257 --> 00:02:39,652
joint assignment. So here we have that,
you know, we can see the that the happiest

32
00:02:39,652 --> 00:02:45,392
assignment as far as A and B are
concerned, in isolation of everything

33
00:02:45,392 --> 00:02:50,762
else, is a0 b0. Okay. This is the case
where neither student has the

34
00:02:50,762 --> 00:02:55,065
misconception. That's the happy
assignment. We see that the second

35
00:02:55,065 --> 00:03:00,296
happiest assignment is a a1, b1 where
again the students agree and in this case

36
00:03:00,296 --> 00:03:05,393
they both have the misconception. And
finally, the other two in the middle are,

37
00:03:05,592 --> 00:03:11,318
are the least happy of all. Now this is a
local happiness, and we have similar notions

38
00:03:11,318 --> 00:03:17,225
of happiness for the other pairs in the
graph. So in this case, we see not only that there is

39
00:03:17,225 --> 00:03:22,914
there a strong sentiment in favor of
agreement, it's much stronger than in the

40
00:03:22,914 --> 00:03:28,457
AB case. So B and C really like to agree
with each other. They you know, it is

41
00:03:28,457 --> 00:03:34,602
very difficult for them to have opposing
opinions. Okay, on the other hand Charles

42
00:03:34,602 --> 00:03:40,000
and Debbie like to argue with each other
all the time, and so if one of them says it's

43
00:03:40,000 --> 00:03:45,052
going to rain today, the other one is
going to say that its sunny today. And so

44
00:03:45,052 --> 00:03:50,588
really you can see that the preferred
assignment for their local opinion is the

45
00:03:50,588 --> 00:03:56,054
ones that they disagree with each
other. Okay? And again A and B like to

46
00:03:56,054 --> 00:04:01,278
agree. So this is sort of a you know
describing the overall state by a bunch of

47
00:04:01,278 --> 00:04:06,087
little pieces and how we are gonna put
these pieces together to define a joint

48
00:04:06,087 --> 00:04:11,339
probability distribution. We are going to
use the notion of product of factors and

49
00:04:11,339 --> 00:04:16,084
so here we are and we are going to take
all these factors and we are gonna

50
00:04:16,084 --> 00:04:20,911
multiply them together. That's great.
Except that there's, this is in no way,

51
00:04:20,911 --> 00:04:26,265
shape, or form a probability distribution,
because it's numbers aren't even in the

52
00:04:26,265 --> 00:04:31,289
interval [0, 1]. Which is why, you'll
notice there's a little tilde on top of

53
00:04:31,289 --> 00:04:42,786
the P. This tilde [indicates un]normalized measure.
Okay? So how do we turn an un-normalized

54
00:04:42,786 --> 00:04:47,771
measure into a probability distribution?
Well, we normalize it. Well actually,

55
00:04:47,771 --> 00:04:52,245
sorry. Before that, here is the
un-normalized measure. So you can see it

56
00:04:52,245 --> 00:04:57,741
here, this, just to sort of highlight the
point, how do we turn this un-normalized

57
00:04:57,741 --> 00:05:02,790
measure into a probability distribution?
We normalize it. And that normalization

58
00:05:02,790 --> 00:05:06,648
here has a name. It's called the
partition function for historical

59
00:05:06,648 --> 00:05:10,795
reasons that come from its origins in
statistical physics, and I'm not even

60
00:05:10,795 --> 00:05:15,329
gonna describe why it's called that, but
that's what it's called. But you can think

61
00:05:15,329 --> 00:05:19,918
of it simply as the normalizing constant
that is going to make all of these sum to

62
00:05:19,918 --> 00:05:24,120
one. So we're gonna get it by simply
summing up all these entries, and that's

63
00:05:24,120 --> 00:05:28,599
going to give us the value Z. And if we
divide all of these entries by Z, we get a

64
00:05:28,599 --> 00:05:32,856
normalized probability distribution. And
that is the probability distribution

65
00:05:32,856 --> 00:05:39,603
that's defined by this graph. So now let's
think about what these factors mean. And

66
00:05:39,603 --> 00:05:45,252
let's think about this factor phi1 of AB,
which is this local happiness between A

67
00:05:45,252 --> 00:05:50,549
and B. And let's think about how it
relates the probability distribution. So

68
00:05:50,549 --> 00:05:56,128
we might think that, this is the marginal
probability of A and B in the joint

69
00:05:56,128 --> 00:06:01,213
distribution. Or maybe it's the
conditional distribution of A given B, or

70
00:06:01,213 --> 00:06:07,770
maybe B given A. Or maybe it's a joint
probability of A and B given C or D. The

71
00:06:07,770 --> 00:06:14,447
answer is, it's none of the above. So,
let's go back and look at what this

72
00:06:14,447 --> 00:06:22,596
actually means in this particular context.
So here we have the set of factors that we

73
00:06:22,596 --> 00:06:29,302
use to construct this distribution. And
here, trust me, is the marginal, marginal

74
00:06:29,302 --> 00:06:38,063
probability of A and B. As defined by the
set of factors PHI. We're going to use a

75
00:06:38,063 --> 00:06:43,289
little PHI here to denote the fact that
it was derived from the set of

76
00:06:43,289 --> 00:07:02,960
factors PHI equals phi1 ... phi n. Oh come on.
[inaudible]. Again phi1, 2, phi3 ...

77
00:07:04,580 --> 00:07:13,048
Okay. So lets compare this
distribution, to the factor phi1. We

78
00:07:13,048 --> 00:07:19,637
can see that not only does it not respect
the fact that A and B like to agree with

79
00:07:19,637 --> 00:07:26,148
each other. Here, A and B like to agree
with each other by a lot. I mean, remember

80
00:07:26,148 --> 00:07:32,261
this is the, this is three times higher
than the next highest value. Here, that

81
00:07:32,261 --> 00:07:38,533
probability has 0.13. And the other high
value assignment in, on this side the

82
00:07:38,533 --> 00:07:44,805
one that had ten, has only 0.04. What is
the single highest assignment here? It's

83
00:07:44,805 --> 00:07:52,773
this one. Let's think about why that is.
This probabiity distribution is constructed

84
00:07:52,773 --> 00:07:58,232
by multiplying all four of these factors.
And if you think about what's going on

85
00:07:58,232 --> 00:08:03,758
here, you see that B really, really likes
to agree with C. So these guys are really

86
00:08:03,758 --> 00:08:12,505
closely tied together. And -- actually this
should probably be [inaudible] -- and A and D similarly

87
00:08:12,505 --> 00:08:20,308
like to agree. So these are really, really
closely tied together. These guys, C and

88
00:08:20,308 --> 00:08:27,913
D, strongly like to disagree. They like to
have opposite values. Now all three of

89
00:08:27,913 --> 00:08:33,468
these factors are actually stronger. That
is the differences between the assignments

90
00:08:33,468 --> 00:08:37,728
are bigger, than in phi1. So where are you
gonna break the cycle. You can't have D

91
00:08:37,728 --> 00:08:41,945
agreeing with A, A agreeing with B, B
agreeing with C and C disagreeing with D,

92
00:08:41,945 --> 00:08:46,436
doesn't work. And so somewhere this cycle
has to be, this loop has to be broken and

93
00:08:46,436 --> 00:08:50,982
the place where it gets broken is A and B
because it's a weaker factor. So the

94
00:08:50,982 --> 00:08:55,144
A and B probability is actually some kind
of complicated aggregate of these

95
00:08:55,144 --> 00:08:59,930
different factors that are used to compose
the Markov network. And this is actually

96
00:08:59,930 --> 00:09:05,428
an important point because it is going to
come back and haunt us in later parts of

97
00:09:05,428 --> 00:09:10,859
the course. There isn't a natural mapping
between the probability distribution and

98
00:09:10,859 --> 00:09:16,290
the factors that are used to compose it.
You can't look at the probability distribution and say

99
00:09:16,290 --> 00:09:21,588
aha, this piece of it is what phi1 ought to be.
This is in direct contrast to Bayesian

100
00:09:21,588 --> 00:09:25,417
network where the [factors] were all
conditional probabilities, and you could

101
00:09:25,417 --> 00:09:29,308
just look at the distribution and compute
them, here you can't do [that]. And, that,

102
00:09:29,308 --> 00:09:33,394
actually turns out to affect things, like
how we can learn these factors from

103
00:09:33,394 --> 00:09:36,847
data, because you can't just extract them
directly from the probability

104
00:09:36,847 --> 00:09:42,303
distribution. So with that definition we
can, with that intuition, we can now go

105
00:09:42,303 --> 00:09:47,071
ahead and define a pairwise Markov
network and I'm defining it exclusively

106
00:09:47,071 --> 00:09:52,019
because pairwise Markov networks are
sufficiently commonly used as a class of

107
00:09:52,019 --> 00:09:57,270
general Markov networks that, that it's
worth giving them they're own place. So a

108
00:09:57,270 --> 00:10:02,941
pairwise Markov network is an
undirected graph whose nodes are the random

109
00:10:02,941 --> 00:10:13,238
variables X1 up to Xn. And we
have edges Xi connecting to Xj and

110
00:10:13,238 --> 00:10:20,432
each one of them is associated with a
factor, also known as a potential, phi i j,

111
00:10:20,432 --> 00:10:27,626
oops, Xi [inaudible] [X]j, okay. That's what -- this shouldn't be
an edge, this should be a comma. That's a

112
00:10:27,626 --> 00:10:33,901
pairwise Markov network and from that.
And here is an example of slightly

113
00:10:33,901 --> 00:10:39,064
larger Markov network, this is a Markov
network that is in the form of a grid and

114
00:10:39,064 --> 00:10:43,747
this is the kind of network that's used
for example when we are doing various

115
00:10:43,747 --> 00:10:48,430
operations on images because then the
variables correspond to pixels for example.

116
00:10:48,643 --> 00:10:54,560
And this is the Markov network that
corresponds to image the segmentation when

117
00:10:54,560 --> 00:10:59,480
we're using super pixels. In which case
it's no longer a regular grid.