1
00:00:00,000 --> 00:00:06,749
A lot of our thinking so far as gone into
constructing algorithms for the problem of

2
00:00:06,749 --> 00:00:12,808
computing marginals in a graphical model.
But as we previously discussed, a very

3
00:00:12,808 --> 00:00:19,020
different type of inference problem, but
one that has many applications in itself

4
00:00:19,020 --> 00:00:24,542
is that of finding a single coherent joint
assignment that has the highest

5
00:00:24,542 --> 00:00:29,623
probability. And we. Showed already that,
that doesn't have the same, that you can't

6
00:00:29,623 --> 00:00:33,915
just solve the marginals problem, and
pick the highest probability assignment

7
00:00:33,915 --> 00:00:38,318
for each variable, and that gives you the
map assignment. That's not what, that's

8
00:00:38,318 --> 00:00:42,889
not what happens. And so we need to have
an alg-, a different set of algorithms for

9
00:00:42,889 --> 00:00:47,181
solving the map problem. And we're going
to talk now about the first of these,

10
00:00:47,181 --> 00:00:53,325
which is, Effectively following the exact
same lines that we did for exact inference

11
00:00:53,325 --> 00:00:59,238
for computing marginals only it turns out
that one can re purpose them with a small

12
00:00:59,238 --> 00:01:05,775
change to computing the map assignment. So the
first operation that going to do in order

13
00:01:05,775 --> 00:01:10,751
to get this to work, is that we are going to take
products and turn them into summations.

14
00:01:10,751 --> 00:01:16,532
And we are going to be doing that by
observing that p of the our distribution p

15
00:01:16,532 --> 00:01:22,963
of Phi is proportional as we know
to a product of factors. And if we, if we

16
00:01:22,963 --> 00:01:30,832
are trying to find the argmax of that
particular product. It can also be

17
00:01:30,832 --> 00:01:39,225
written, reformulated as the argmax of
summation where each of these theta ks

18
00:01:39,225 --> 00:01:45,706
is the log. Of the potential phi of k. Which is
basically the same as taking the table

19
00:01:45,706 --> 00:01:52,130
that represents the factor and converting
each entry into its logarithm. And that

20
00:01:52,130 --> 00:01:58,710
gives you something that, rather than
being a product of factors, is the sum of

21
00:01:58,710 --> 00:02:04,786
these log factors. And there's really good
reasons for doing that. First, because

22
00:02:04,786 --> 00:02:09,577
summations are easier to handle than, than
products. But also because, if you're

23
00:02:09,577 --> 00:02:14,192
multiplying a whole bunch of very small
numbers, you're going to get numerical

24
00:02:14,192 --> 00:02:18,865
underflows. And converting this into
summations is a much more robust algorithm

25
00:02:18,865 --> 00:02:25,115
numerically, in, in terms of a practical
implementation. And so now we are going to

26
00:02:25,115 --> 00:02:30,859
consider the problem, of that we just
wrote here which is the argmax of an

27
00:02:30,859 --> 00:02:37,302
expression that we are going to call theta
of X1 up to Xn which is defined as the

28
00:02:37,302 --> 00:02:45,467
sum of factors over smaller scopes which
are these theta ks. And this is the

29
00:02:45,467 --> 00:02:51,351
example that I meant to show a moment ago.
So this is taking a factor over scope A

30
00:02:51,351 --> 00:02:56,804
and B, and converting it to its log
factor, by taking log base two. And you'll

31
00:02:56,804 --> 00:03:02,472
notice that the numbers were carefully
selected to give me nice, outputs. But

32
00:03:02,472 --> 00:03:10,035
that doesn't have to be the case. So now
that we've reduced problem to one that

33
00:03:10,035 --> 00:03:15,717
we're taking the max over summation, we're
going to now go back to our simple example

34
00:03:15,717 --> 00:03:21,400
of a chain and we're going to think about
how we can do max sum variable elimination

35
00:03:21,400 --> 00:03:26,297
in chain. And this is going to look.
Almost identical to the max, to the sum

36
00:03:26,297 --> 00:03:31,675
product algorithm that we had before. So
let's understand what we are trying to do

37
00:03:31,675 --> 00:03:36,724
here. So we're trying, assuming what we
are trying to do now is, forget the arg

38
00:03:36,724 --> 00:03:43,656
max, let's assume that we just want to
find the max of this of this. Expression

39
00:03:43,656 --> 00:03:54,075
theta of A, B. C, D and E. And so just
like in the sum product case, we can break

40
00:03:54,075 --> 00:04:00,774
up the maxes into a max over A and then a
max over B and a max over C and a max over

41
00:04:00,774 --> 00:04:07,315
D. And while we might not be quite as used
to doing this kind of operation that I'm

42
00:04:07,315 --> 00:04:13,698
about to show, it's equally valid to point
out, that because none these guys, theta

43
00:04:13,698 --> 00:04:22,229
two, theta three or theta four depend on A
we can. Add them up, the max over this

44
00:04:22,229 --> 00:04:32,119
guy, over theta one and AB, after
completing the max. And so that's going to

45
00:04:32,119 --> 00:04:40,636
give me a factor here. Which, which looks
like max over A, theta one of AB. And I'm

46
00:04:40,636 --> 00:04:46,152
going to call that Lambda one of B.
Because notice that this is not a

47
00:04:46,152 --> 00:04:52,708
constant. It's a function that depends on
B. For different values of B, you're gonna

48
00:04:52,708 --> 00:04:58,944
have different val-, different A's of
maximize, and different values of the max

49
00:04:58,944 --> 00:05:05,340
expression. And so this Lambda one of B is
simply the max over A of theta one, AB.

50
00:05:05,900 --> 00:05:12,803
And that process has effectively now
eliminated A from this expression, and

51
00:05:12,803 --> 00:05:20,108
given me a maximization problem over one
fewer variable, only B, C, D, and E. Just

52
00:05:20,108 --> 00:05:24,543
like in the context of sum product
algorithms, we can view all of these

53
00:05:24,543 --> 00:05:29,411
operations as operations over factors,
rather than just thinking about them in

54
00:05:29,411 --> 00:05:34,340
terms of expression. So whereas before we
defined things like factor product and

55
00:05:34,340 --> 00:05:39,330
factor marginalization, we can now define
analogous operations that correspond to

56
00:05:39,330 --> 00:05:44,136
factor summation and factor maximization.
So factor summation's a very obvious

57
00:05:44,136 --> 00:05:49,003
operation, does exactly what we did here,
so if we want to, in the case of factor

58
00:05:49,003 --> 00:05:55,250
product, if we want to define. In the row
for A1, B1, C1, we're going to add up. The

59
00:05:55,250 --> 00:06:01,309
entry three from A1 B1. And the entry four
from B1C1 and that is going to give me

60
00:06:01,309 --> 00:06:06,306
seven. And I can similarly define all of
the other entries in the factor summation

61
00:06:06,306 --> 00:06:12,462
which we're showing here on the right.
Factor maximization is same way that we

62
00:06:12,462 --> 00:06:19,634
could sum marginalize a factor. This is
something that max marginalizes, is called

63
00:06:19,634 --> 00:06:28,818
the max marginalization. And what it does
is, it looks, if I, so I'm trying to get

64
00:06:28,818 --> 00:06:35,872
rid of B. I have these two rows here. Say,
for example, A1, B1, C1. And A1, B2, C1,

65
00:06:35,872 --> 00:06:42,925
that only differ on B. And my new entry
here, A1, C1, is going to be the max of

66
00:06:42,925 --> 00:06:49,521
these two entries over here. Which, in
this case, is going to be seven. And

67
00:06:49,521 --> 00:06:57,190
similarly for, say, A1-C2. I am going to
end up with a max of 4.5 and two which is

68
00:06:57,190 --> 00:07:02,522
4.5. So this is another form of
marginalization where I remove a variable

69
00:07:02,522 --> 00:07:08,332
B but using an operation other than
summation. So now that we've defined these

70
00:07:08,332 --> 00:07:14,402
two operations, we can go back and define
the max sum variable elimination in

71
00:07:14,402 --> 00:07:20,551
chains, as a set of factor operations.
Where I eliminate A, then B, and so on and

72
00:07:20,551 --> 00:07:26,069
so forth. So, for example, having
eliminated A as in the previous step, I

73
00:07:26,069 --> 00:07:32,533
can now do the exact same operation by
noticing that the only factors that depend

74
00:07:32,533 --> 00:07:39,151
on B are theta two of B, and lambda one of
B. So these other two. I can move outside

75
00:07:39,151 --> 00:07:45,643
of the maximization. And that's going to
give me a max over B of a factor that is

76
00:07:45,643 --> 00:07:51,643
the sum of the two factors Theta 2BC and
Lambda one of B that I got from the

77
00:07:51,643 --> 00:07:57,386
previous elimination step. And that's 
going to give me a new factor lambda 2 of C

78
00:07:57,386 --> 00:08:02,834
and the process continues. In exactly the
same way as variable elimination did for

79
00:08:02,834 --> 00:08:11,509
the case of sum product. And that's basically
the algorithm. So now let's think about

80
00:08:11,509 --> 00:08:18,834
what we get at the end of this execution,
for the final factor. What is Lambda four,

81
00:08:18,834 --> 00:08:25,729
having gone through Lambda two and Lambda
three, and now we get Lambda four of e.

82
00:08:25,729 --> 00:08:34,889
What is Lambda four for a given value,
little e? Lambda four of little e is what

83
00:08:34,889 --> 00:08:49,158
we got by maximizing. Over A, B, C and D
of theta A, B, C and D. So this is, the

84
00:08:49,158 --> 00:09:00,080
best possible assignment. The best value.
That I can get, that I can possibly get.

85
00:09:01,240 --> 00:09:14,189
If, we mandate that E equals little e.
Okay. And so, this is a factor, and it

86
00:09:14,189 --> 00:09:21,316
gives me that value, for each one of the,
value score, the, effectively, for each

87
00:09:21,316 --> 00:09:33,845
value little e of E. This is called a max
marginal. In the same way that we took

88
00:09:33,845 --> 00:09:40,117
variable elimination for sum product and
we used that to define a clique tree

89
00:09:40,117 --> 00:09:45,846
algorithm, we can do exactly the same
thing for max product, for er, max sum,

90
00:09:45,846 --> 00:09:51,576
using the exact same type of data
structure. So here we def, we're going to

91
00:09:51,576 --> 00:09:57,461
use the exact same clique tree, and we
have cliques over AB, BC, CD, and DE. And

92
00:09:57,693 --> 00:10:06,145
we're going to as, as usual, assign the
potentials. To the appropriate, cliques

93
00:10:06,145 --> 00:10:14,983
using. The family preservation property.
And now let's go ahead and see how

94
00:10:14,983 --> 00:10:21,230
messages are passed, in this, clique tree
architecture So initially, the AB clique

95
00:10:21,230 --> 00:10:27,245
is going to define the message lambda 1-2,
which is obtained by maximizing out A over

96
00:10:27,245 --> 00:10:32,906
theta one. And the resulting message over
B gets passed to clique two. Clique two

97
00:10:32,906 --> 00:10:38,496
can take that message; multiply it with
its own, factor, theta two. And add that,

98
00:10:38,496 --> 00:10:44,015
this is max sum, remember? I'm going to
add that to lambda 1-2, and that gives me

99
00:10:44,015 --> 00:10:49,300
the message lambda 2-3. And the same thing
can happen when clique three passes a

100
00:10:49,300 --> 00:10:53,517
message to clique four in this case over
the scope of E. So exactly the same

101
00:10:53,517 --> 00:10:58,305
message passing process except using max
and sum instead of sum and product. We can

102
00:10:58,305 --> 00:11:04,197
equally well pass messages in the other
direction. So four to three over scope D

103
00:11:04,197 --> 00:11:10,872
three to two and two to one. And all the
properties that we said hold in the

104
00:11:10,872 --> 00:11:16,893
context of sum product clique trees hold
here as well. First notice for example,

105
00:11:16,893 --> 00:11:23,064
that once this message lambda one two is
sent, it never changes again. It's, it's

106
00:11:23,064 --> 00:11:29,161
defined once and for all. Lambda two
three, once it receives the message lambda

107
00:11:29,161 --> 00:11:34,956
one two, it too has stabilized and will
never change, and similarly for lambda

108
00:11:34,956 --> 00:11:40,480
three four. So we can do one pass. From
left to right to compute all of the left

109
00:11:40,480 --> 00:11:45,703
to right messages. And a similar pass
right to left to compute all of the right

110
00:11:45,703 --> 00:11:51,390
to left messages. And as soon as we do
that, they've all converged. The second

111
00:11:51,390 --> 00:11:58,920
thing to notice is what is the value of
this clique over here. So, if we look at

112
00:11:58,920 --> 00:12:06,083
this, we can see that when I've compute,
when I finally get all of the messages

113
00:12:06,083 --> 00:12:13,181
from both sides, I have integrated in
theta one. Theta two, theta three which is

114
00:12:13,181 --> 00:12:20,181
stored in the clique itself, and
theta four coming in from the message on

115
00:12:20,181 --> 00:12:27,181
the right, and maximize out all of the
variables A, B, and E so that what I have

116
00:12:27,181 --> 00:12:34,180
left is a factor over the clique three
which is the max over A, B, and E of the

117
00:12:34,180 --> 00:12:40,864
sum of all of the factors in this network.
So, just to summarize, once the clique I

118
00:12:40,864 --> 00:12:47,216
receives the final message from all of its
neighbors except c j, then that message is

119
00:12:47,216 --> 00:12:53,044
also final, will never change, and the
messages from all leaves are immediately

120
00:12:53,044 --> 00:12:59,247
final. And so what we have is an algorithm
that at convergence, that converges after

121
00:12:59,247 --> 00:13:04,702
two passes and gives us correct max
marginals at every single one of the

122
00:13:04,702 --> 00:13:11,963
cliques. So. Let's take a simple example
just to convince ourselves that this is

123
00:13:11,963 --> 00:13:18,712
doing the right thing. So, I'm looking now
at a much simpler [inaudible] that only

124
00:13:18,712 --> 00:13:24,978
has a, b, and c. So, there's is two
factors one over theta one of ab and theta

125
00:13:24,978 --> 00:13:36,790
two of BC. And first we are going to
construct the overall math theta which is

126
00:13:36,790 --> 00:13:44,952
the sum of theta one and theta two. So this
is a factor summation [inaudible] this

127
00:13:44,952 --> 00:13:51,602
expression. And let's look at it and see
what is the map assignment in this

128
00:13:51,602 --> 00:13:58,082
example. And if we just look at the
numbers that we computed, we see that the

129
00:13:58,082 --> 00:14:05,785
map assignment is A1 B1 C1 with a value of
seven. Now let's look at the message

130
00:14:05,785 --> 00:14:10,780
passings, process that you will have, on
this, very simple clique tree with two

131
00:14:10,780 --> 00:14:17,665
cliques. So, this is theta one, it's
assigned to clique one. Theta two is

132
00:14:17,665 --> 00:14:25,581
assigned to clique two. And let's look at
the two messages that are passed. So, here

133
00:14:25,581 --> 00:14:33,980
was my a one so a b passes a message to b
c, and that message is the max marginal.

134
00:14:34,260 --> 00:14:42,901
Max marginalization over the variable a.
And so we can see here we have a max

135
00:14:42,901 --> 00:14:51,326
between three and, and -one so we get
three, because this is the max over the

136
00:14:51,326 --> 00:15:00,183
two values of a that are consistent with b
one. And for b two we have the max over

137
00:15:00,183 --> 00:15:07,617
zero and one so we get one. >> And exactly
the same process gives us, for this

138
00:15:07,617 --> 00:15:14,429
message, where I'm max marginalizing C, I
get this message. This path from left to

139
00:15:14,429 --> 00:15:20,259
right. Now each of these two cliques takes
its message, and note this is, I've gotten

140
00:15:20,259 --> 00:15:25,179
immediate convergence here because there
was only one message to pass in each

141
00:15:25,179 --> 00:15:30,035
direction. And, so what I get here is the
sum of this factor plus the incoming

142
00:15:30,035 --> 00:15:37,654
message. I've added these two together and
so I have for example, for the first row

143
00:15:37,654 --> 00:15:43,567
A1, for A1B1, I have three from here and
four from here. So I get three + four

144
00:15:43,567 --> 00:15:52,944
which is equal to seven. For a1, b2, I get
a zero from here, and a2 from there, zero

145
00:15:52,944 --> 00:16:01,982
+ two = two. And I can do exactly the same
operation to get this, to get this, set,

146
00:16:01,982 --> 00:16:08,548
to get this factor on the right. I get
that by summing up this, with that, and I

147
00:16:08,548 --> 00:16:15,789
get this factor over here. And you'll
notice that miraculously. The map, the map

148
00:16:15,789 --> 00:16:22,692
had each of these factors separately. Is
a1 b1 on the left and b1 c1 on the right?

149
00:16:22,692 --> 00:16:29,398
So sure enough what I got here was the
most likely assignment consistent with a1

150
00:16:29,398 --> 00:16:35,044
b1 and over here the most likely
assignment consistent with b1c2. And

151
00:16:35,044 --> 00:16:40,203
you'll notice, if you go back and check,
and I'm not going to do that right now.

152
00:16:40,203 --> 00:16:45,097
But if you go back and check this, big
table over here, you can convince

153
00:16:45,097 --> 00:16:50,255
yourselves that this doesn't only hold
true for A1-B1. If you look, for example,

154
00:16:50,255 --> 00:16:55,480
at A2-B1, you'll see that what you get
here, the value three, is the value of the

155
00:16:55,480 --> 00:17:00,374
most likely assignments that are
consistent, that is consistent with A2-B1.

156
00:17:00,374 --> 00:17:06,061
So actually, let's go back and check that.
So here is A2-B1. We have two assignments

157
00:17:06,061 --> 00:17:11,717
consistent with A two B one, one is 0.5
and one is three. Three is the best one,

158
00:17:11,717 --> 00:17:16,717
and sure enough the value that we get here
is three. So, it all works. So what can we

159
00:17:16,717 --> 00:17:20,994
say about this algorithm once it
converges? The important thing is that we

160
00:17:20,994 --> 00:17:25,561
can compute beliefs at each clique that
represent exactly the max marginals of

161
00:17:25,561 --> 00:17:30,301
that clique. So how do we compute these
beliefs? Analogously to what we had in the

162
00:17:30,301 --> 00:17:34,751
context of sum product, we look at the
factor assigned to the clique, which is

163
00:17:34,751 --> 00:17:39,855
the theta I. And we add to it the incoming
messages. Before you remember we had the

164
00:17:39,855 --> 00:17:45,556
factor assigned to the clique multiplied
by the incoming message because we were

165
00:17:45,556 --> 00:17:51,396
doing products instead of summations. What
does this belief, what does this belief

166
00:17:51,396 --> 00:17:57,553
encode? This belief the max marginal. So
specifically, it, we can consider for any

167
00:17:57,553 --> 00:18:04,349
given assignment to the clique Ci we can
look at the best possible, the score of

168
00:18:04,349 --> 00:18:11,570
the best possible completion to the clique
Ci and that is the value of the belief at

169
00:18:11,570 --> 00:18:17,542
that clique. So it's the max over all of
the variables, WI, that are not assigned

170
00:18:17,542 --> 00:18:23,012
to the clique. One important
consequence of the fact that we have max

171
00:18:23,012 --> 00:18:29,039
marginals is that we get a, a calibration
property here as well. So, f, the cliques

172
00:18:29,039 --> 00:18:35,162
must agree on the variables that they
share. So to understand this let, let's

173
00:18:35,162 --> 00:18:42,091
look at these two cliques that we have in
the simple 2-clique example. And here are

174
00:18:42,091 --> 00:18:48,537
the beliefs that we had for clique one,
and for clique two. It's the sum of theta

175
00:18:48,537 --> 00:18:58,265
one plus the incoming message over here.
And theta two plus nine over two. And,

176
00:18:58,265 --> 00:19:05,296
let's look at what the calibration
property tells us. It tells us that, for

177
00:19:05,296 --> 00:19:11,597
example, if we look at. The implications
of this clique regarding the variable b.

178
00:19:11,808 --> 00:19:17,658
We would have that, that the, this clique
tells us that the best possible completion

179
00:19:17,658 --> 00:19:23,297
for b one has a score of seven, and the
best possible completion for b two has a

180
00:19:23,297 --> 00:19:28,653
score of three. This clique, if we look at
it, tells us that the best possible

181
00:19:28,653 --> 00:19:34,080
completion for b1 also has a score of
seven, and the best possible completion

182
00:19:34,080 --> 00:19:39,648
for b two also has a score of three. So
these two cliques agree regarding their

183
00:19:39,860 --> 00:19:43,897
regarding the variable in their
shared scope, which is the variable

184
00:19:43,897 --> 00:19:48,941
B. So to summarize, we can apply, in the
context of max sum, exactly the same

185
00:19:48,941 --> 00:19:54,077
clique tree algorithm used for sum
product. Messages are passed in the same

186
00:19:54,077 --> 00:19:59,556
way. The clique trees is constructed in
the same way. The only difference is that

187
00:19:59,556 --> 00:20:05,035
the message passing operations use max and
sum as opposed to sum and product. At

188
00:20:05,035 --> 00:20:10,508
exactly, as in sum product, convergence is
[inaudible], achieved after a single up

189
00:20:10,508 --> 00:20:15,707
and down pass. And the result of that is a
set of beliefs that represent max

190
00:20:15,707 --> 00:20:20,701
marginals at each of those cliques.
Where, as a reminder, the max marginals

191
00:20:20,701 --> 00:20:26,105
tells for each assignment, what is the
score of the best possible completion to

192
00:20:26,105 --> 00:20:27,200
that assignment.