We previously showed a cleaved tree algorithm for performing maximal message

passing. But we didn't talk about how one can take

the output of that algorithm and construct an actual map assignment.

We just showed how we can get max marginals.

So how do we compute a map assignment? Well it turns out that this task is easy

as our examples already indicated if the map assignment is unique.

Because at that point we have a single maximizing assignment at each clique.

And we've already seen that the value of that maximizing assignment is the theta

value of the map assignment. So in our example that we showed before,

we had, the A1B1C1 assigned, as the MAP assignment.

And we saw that A1B1 was maximizing assignment in clique 1, and B1C1 was the

maximizing assignment at clique 2. And we also saw that due to the

calibration property, the choices of all of these cliques must agree.

Which means that it doesn't really matter whether we pick the value of b from this

clique, or from that clique, because they are going to give us exactly the same

answer. So that's all well and good but what

happens is life is not as kind to us. So if the MAP assignment is not unique

then we might have multiple choices at some of the cliques and we might have to

make a decision. So for example imagine that at

calibration, at convergence of the subproduct algorithm we have these two

cliques over here and we can see that in this clique over here we have two

assignments, A1 B1 and A2 B2, both of which have the value 2.

And this clique over here, once again, we have two maximizing

assignments. And the problem is, we can't now look

separately at each of those cleaks and pick an assignment because, at that point

we might pick say, this assignment and this clique.

And this assignment and that clique. And now we have a conflict regarding the

value of the variable V. And it's not just a matter of saying

well, okay let's forget for example, the fact that we picked the value B2 in this

clique over here. Because what you, because we also picked

the value C2. And intuitively we can see that C2 goes

with B2 and not with B1. So the value A1, B1,

the assignment A1, B1, C2 is not a good MAP assignment.

So what we need to do is we need to pick, not this one, but rather B1 C1 in the

second clique in order to reorder the first clique.

And so what we see the arbitrary tie breaking may not produce an actual map

assignment. So, how do we actually address this

problem, it turns out there's two main choices in terms of the solution.

The first is to tweak the problem a little bit, so as to make the MAP

assignment unique. So, for example if we add a tiny random

perturbation to all of our factors. Then with probability that's effectively

one, there's going to be unique map assignment.

At which point, we can go ahead and use the solution that we had if the MAP

assignment was unique. The second is, to use a procedure that

picks assignments one at a time, building a map assigned clique by clique.

So we start out with the AB clique. We pick A1B1.

And then when we go down to the next clique down the line, we remember that we

picked B1. And we only are allowed to now pick an

assignment that's consistent with B1. And that turns out to be an alternative

algorithm that who's complexity is effectively the same as that of

calibrating the clique tree to begin with.

And so it's not more expensive. Each of these options is a very

reasonable option and both are used in practice for decoding the MAP assignment

from a calibrated a clique tree.