1
00:00:00,000 --> 00:00:04,586
We previously showed a clique tree
algorithm for performing max sum message

2
00:00:04,586 --> 00:00:09,595
passing. But, we didn't talk about how one
can take the output of that algorithm and

3
00:00:09,595 --> 00:00:14,303
construct an actual map assignment. We
just showed how we can get max

4
00:00:14,303 --> 00:00:19,257
marginals. So how do we compute a map
assignment? Well it turns out this task is

5
00:00:19,257 --> 00:00:24,700
easy as our examples already indicated, if
the map assignment is unique. Because at

6
00:00:24,700 --> 00:00:29,678
that point we have a single maximizing
assignment at each clique. And we've

7
00:00:29,678 --> 00:00:34,789
already seen, that the value of that
maximizing assignment is the theta value

8
00:00:34,789 --> 00:00:39,597
of the map assignment. So in our example
that we showed before we had the A1B1C1

9
00:00:39,597 --> 00:00:43,926
assigned as the map assignment and we saw
that the A1B1 was the maximizing

10
00:00:43,926 --> 00:00:48,486
assignment in clique1 and B1C1 was the
maximizing assignment at clique2 and we

11
00:00:48,486 --> 00:00:52,758
also saw that due to the calibration
property the choices of all of these

12
00:00:52,758 --> 00:00:57,606
cliques must agree which means it doesn't
really matter whether we picked the value

13
00:00:57,606 --> 00:01:02,166
of B from this clique or that clique
because they are going to give us exactly

14
00:01:02,166 --> 00:01:07,331
the same answer. So that's all well and
good, but what happens is life is not as

15
00:01:07,331 --> 00:01:12,736
kind to us? So if the Map assignment is
not unique then we might have multiple

16
00:01:12,736 --> 00:01:17,798
choices at some, of the cliques and we
might have to make a decision. So for

17
00:01:17,798 --> 00:01:23,545
example, imagine that, at calibration, at
convergence of the some part of algorithm,

18
00:01:23,545 --> 00:01:29,155
we have these two cliques over here and we
can see that in this clique over here, we

19
00:01:29,155 --> 00:01:34,423
have two assignments, A1-B1 and A2-B2,
both of which have the value two. And at

20
00:01:34,423 --> 00:01:40,358
this clique over here, once again we
have two maximizing assignments. And the

21
00:01:40,358 --> 00:01:45,658
problem is we can't now look separately at
each of those cliques and pick an assignment

22
00:01:45,658 --> 00:01:50,647
because at that point we might pick,
say, this assignment in this clique and

23
00:01:50,647 --> 00:01:55,884
this assignment in that clique and now we
have a conflict in regarding the value of

24
00:01:55,884 --> 00:02:01,643
the variable B. And it's not just a matter
of saying, well, okay let's forget, for

25
00:02:01,643 --> 00:02:07,899
example, the fact that we picked the value
B2 in this clique over here because what

26
00:02:07,899 --> 00:02:13,929
you, because we also picked the value C2
and intuitively we can see that C2 goes

27
00:02:13,929 --> 00:02:19,582
with B2 and not with B1. So the value A1
B1, the assignment A1, B1, C2 is not a

28
00:02:19,582 --> 00:02:26,110
good map assignment. So what we need to do
is we need to pick. Not this one, but

29
00:02:26,110 --> 00:02:33,588
rather B1C1 in the second clique in order
to agree with the first clique. And so,

30
00:02:33,588 --> 00:02:39,088
what we see that arbitrary tie breaking may
not produce and actual map assignment. So,

31
00:02:39,088 --> 00:02:44,589
how do we actually address this problem?
It turns out there's two main choices in

32
00:02:44,589 --> 00:02:50,074
terms of the solution. The first is to
tweak the problem a little bit so as to

33
00:02:50,074 --> 00:02:55,275
make the map assignment unique so, for
example if you add a tiny random

34
00:02:55,275 --> 00:03:01,126
perturbation to all of our factors, then
with probability that's effectively one there's

35
00:03:01,126 --> 00:03:06,977
going to be a unique map assignment at
which point we can go ahead and use the

36
00:03:06,977 --> 00:03:12,297
solution that we had if the map
assignment was unique. [sound] The second

37
00:03:12,297 --> 00:03:17,666
is to use a procedure that picks
assignments one at a time, building a map

38
00:03:17,666 --> 00:03:23,175
assignment clique by clique. So, we start
out with the AB clique, we pick A1 B1. And

39
00:03:23,175 --> 00:03:28,753
then, when we go down to the next clique
down line, we remember that we picked B1

40
00:03:28,753 --> 00:03:34,541
and we only are allowed to now pick an
assignment that's consistent with B1. And,

41
00:03:34,541 --> 00:03:39,701
that turns out to be an alternative
algorithm that whose complexity is

42
00:03:39,701 --> 00:03:44,370
effectively the same as that of
calibrating the clique tree to

43
00:03:44,370 --> 00:03:48,917
begin with. And, so it's not more
expensive. Each of these options is a very

44
00:03:48,917 --> 00:03:54,352
reasonable option. And both are used in
practice for decoding the map assignment

45
00:03:54,352 --> 00:00:00,000
from a calibrated er clique tree.