1
00:00:00,760 --> 00:00:10,576
[sound] As we said, there's many different
kinds of queries that one can use a

2
00:00:10,576 --> 00:00:17,004
graphical model to answer. Conditional
probability queries are m-, very commonly

3
00:00:17,004 --> 00:00:23,514
used, but another commonly used type of
inference is what's called MAP inference.

4
00:00:23,514 --> 00:00:29,780
So what is MAP inference? Map stands as a
shorthand for what's c-, for

5
00:00:30,409 --> 00:00:36,290
Maximum a Posteriori and it's defined as follows,
here we have a set of evidence o-,

6
00:00:36,290 --> 00:00:42,630
observations, little e over some variables
E. And we have a query Y, and it turns out

7
00:00:42,630 --> 00:00:49,198
that for computational reasons that we're
not going to discuss for the moment, it's

8
00:00:49,198 --> 00:00:54,545
important that the set of Ys is
everything, all of the variables other

9
00:00:54,545 --> 00:01:07,072
than e. So now, our task is to compute
what's called the map assignment, which is

10
00:01:07,072 --> 00:01:14,264
the Y, the assignment little Y to the
variables Y that maximizes the conditional

11
00:01:14,264 --> 00:01:21,815
probability of, the variables Y given the
evidence. Now, so for those of you who

12
00:01:21,815 --> 00:01:28,965
haven't seen the notation argmax,
argmax is the Y. That provides the maximal

13
00:01:28,965 --> 00:01:35,124
value to this expression over here. Now,
note that, in some cases, this maximizing

14
00:01:35,124 --> 00:01:40,698
value might not be unique. That is, there
might be several different assignments.

15
00:01:40,698 --> 00:01:46,130
Say one, Y1 and Y2 that give the exact
same probability. And so the map is not

16
00:01:46,130 --> 00:01:52,289
necessarily a unique, assignment. This has
many applications, some of which we've

17
00:01:52,289 --> 00:01:57,220
discussed before. So in the context of
message decoding, for example, where we

18
00:01:57,220 --> 00:02:02,606
have a set of noisy bits that are passed
over the channel, over noisy communication

19
00:02:02,606 --> 00:02:07,927
channel, what we often want to get is the
most likely message that was transmitted,

20
00:02:07,927 --> 00:02:13,117
that is as assignment to the transmitted
bits that is the most likely given our

21
00:02:13,117 --> 00:02:17,789
evidence. In the context of image
segmentation, we would like to take the

22
00:02:17,789 --> 00:02:22,619
pixels and figure out the most likely
assignment of pixels to, to semantic

23
00:02:22,619 --> 00:02:28,729
category. So both of these can be
viewed as map assignment problems. Now, an

24
00:02:28,729 --> 00:02:33,697
important thing to understand about map,
is it really is a different problem than

25
00:02:33,697 --> 00:02:37,930
conditional probability queries. So
understand that, let's look at the

26
00:02:37,930 --> 00:02:42,959
following very simple example over just
two random variables. So here we have, a

27
00:02:42,959 --> 00:02:47,989
Bayesian network over the variables A and
B. And if you multiply the two CPDs, it's,

28
00:02:48,173 --> 00:02:52,835
you get the joint distribution shown over
here. And it's not, and it's fairly

29
00:02:52,835 --> 00:02:57,803
immediate to see that the map assignment
is this one, because it has the highest

30
00:02:57,803 --> 00:03:03,574
probability. Can we get at the map
assignment by looking separately at the

31
00:03:03,574 --> 00:03:09,908
variable A and at the variable B? So if we
look at that we see that if we look

32
00:03:09,908 --> 00:03:16,486
separately at the variable A the most
likely assignment to the variable A is A-1

33
00:03:16,486 --> 00:03:22,592
as opposed to, in the map assignment, the
variable A took the value A0. And so, we

34
00:03:22,592 --> 00:03:28,958
can't look separately at the marginal over
A and over B and use that to infer the map

35
00:03:28,958 --> 00:03:34,954
assignment. And the reason is that we're
looking for a single assignment over all

36
00:03:34,954 --> 00:03:40,774
of the variables, that together has, has
the highest probability. Unfortunately,

37
00:03:40,774 --> 00:03:45,845
just like the conditional probability
inference, however, this problem, too, is

38
00:03:45,845 --> 00:03:50,983
NP hard. So, again, let's formalize what,
exact problem is at the heart of this

39
00:03:50,983 --> 00:03:56,321
context. And it, and so here is, again,
one example of an NP hard problem in

40
00:03:56,321 --> 00:04:01,659
the context of map, which is just to find
the joint assignment with the highest

41
00:04:01,659 --> 00:04:07,754
probability. It's not the only NP hard
problem. Here is another one. Figuring out

42
00:04:07,754 --> 00:04:14,076
what for given probabilistic graphical
model and some threshold little P, whether

43
00:04:14,076 --> 00:04:20,714
there exists an assignment little X whose
probability is great than P. That problem,

44
00:04:20,714 --> 00:04:25,238
too, is NP Hard. So, should we give up?
Well, just like in the context of

45
00:04:25,238 --> 00:04:30,493
conditional probability queries the answer
is no. And, there is algorithms that can

46
00:04:30,679 --> 00:04:35,625
solve this problem very efficiently and
fast in an even broader set of problems

47
00:04:35,625 --> 00:04:41,601
than for conditional probability queries.
So let's again look deeper into this

48
00:04:41,601 --> 00:04:48,325
problem, and understand the foundations of
what might make it tractable. So. Going

49
00:04:48,325 --> 00:04:54,274
back to our example of a Bayesian network.
Once again we are going to view CPDs as

50
00:04:54,274 --> 00:05:00,440
factors so here P of C again translates into
a factor over C just like before and whereas

51
00:05:00,440 --> 00:05:06,462
in the case of conditional probability
queries, we wanted to sum out some of the

52
00:05:06,462 --> 00:05:11,758
variables, marginalize them. Now we're
going to, to, what to find the argmax

53
00:05:11,758 --> 00:05:17,706
which is the assignment of these variables
which maximizes the product. So here we

54
00:05:17,706 --> 00:05:23,149
have the max. Of a product which is why
this is often called a max product

55
00:05:23,149 --> 00:05:29,363
problem. Let's break down the max product
problem. So imagine that we in more

56
00:05:29,363 --> 00:05:35,679
general have. In more general case have a
probability over y. Given E equal little e.

57
00:05:35,679 --> 00:05:42,230
And [inaudible] remind ourselves that y is
a. Is the set of all variables. Other than

58
00:05:42,230 --> 00:05:48,391
the ones in e. And so by the definition of
conditional probability. We have this

59
00:05:48,391 --> 00:05:54,552
ratio. Who's what we're trying to find is
the maximal y. The maximize to this

60
00:05:54,552 --> 00:06:04,274
ratio. And notice that the denominator. Is
constant relative to y. Sorry, yes, with

61
00:06:04,274 --> 00:06:10,650
respect to y. Which means that, for the
purpose of finding the maximum y, we don't

62
00:06:10,650 --> 00:06:17,106
really care about the denominator, only
the numerator, which is the probability of

63
00:06:17,106 --> 00:06:22,765
y comma e equals little e, the
unnormalized, an unnormalized measure. The

64
00:06:22,765 --> 00:06:29,141
probabil-, this numerator, in the general
case, is a product of factors normalized

65
00:06:29,141 --> 00:06:34,960
by the partition function, where the
factors here are the reduced factors.

66
00:06:35,740 --> 00:06:47,540
Reduced relative to the evidence. [sound].
Once again we notice, that, this, is the

67
00:06:47,540 --> 00:06:57,556
partition function, and it's constant.
Relative to y. Which means that we can

68
00:06:57,556 --> 00:07:03,433
ignore it. And, so, once again we have
this, the expression is now proportional

69
00:07:03,433 --> 00:07:09,697
to a product of the same reduced factors.
And so what we're trying to do is we're

70
00:07:09,697 --> 00:07:18,187
trying to maximize a product of factors in
this more general case as well. Which

71
00:07:18,187 --> 00:07:24,730
gives us the following as the optimization
problem. There's many algorithms that can

72
00:07:24,730 --> 00:07:30,650
solve the map problem. The first is
analogous to algorithms for sum product.

73
00:07:30,884 --> 00:07:37,193
These algorithms take the maximization
operation, and pushes that into the factor

74
00:07:37,193 --> 00:07:44,189
product. Giving rise to a max product
variable elimination algorithm. We

75
00:07:44,189 --> 00:07:48,744
also have message passing algorithms,
which, again, are a direct analog to

76
00:07:48,744 --> 00:07:53,741
algorithms for sum product. And they give
rise to a class of algorithms called

77
00:07:53,741 --> 00:07:58,486
max product belief propagation.
However, because the map problem is

78
00:07:58,486 --> 00:08:03,572
intrinsically an optimization problem.
One can also call in techniques that are

79
00:08:03,572 --> 00:08:09,129
specific to optimization. And the class of
such methods include methods that are based

80
00:08:09,129 --> 00:08:14,111
on integer programming. Which is a general
class of optimization over discreet

81
00:08:14,111 --> 00:08:19,221
spaces. It turns out that this class of 
methods that build on integer programming

82
00:08:19,221 --> 00:08:24,011
techniques is one of the most popular
methods in the last few years. And has

83
00:08:24,011 --> 00:08:29,185
given rise to a whole new range of map algorithms that are considerably better

84
00:08:29,185 --> 00:08:33,593
than in any of the previous algorithms developed up to that point so

85
00:08:33,593 --> 00:08:37,770
especially for the approximate case.
[sound] It also turns out that, for

86
00:08:37,770 --> 00:08:43,861
certain types of networks, that, some of
which we'll discuss, there are specific

87
00:08:43,861 --> 00:08:49,876
algorithms that are very efficient for
that particular class of, of graphical

88
00:08:49,876 --> 00:08:55,741
model. And one of those, perhaps the most
commonly used, but not the only one, is,

89
00:08:55,967 --> 00:09:01,566
methods based on, a class of algorithms
called graph cuts. And. And finally,

90
00:09:01,566 --> 00:09:06,806
because it's a optimization problem one
can also use standard search techniques

91
00:09:06,806 --> 00:09:11,980
over combinatorial search spaces. And
there are problems for which this is also

92
00:09:11,980 --> 00:09:17,702
a very useful and successful solution. So
to summarize, the map problem aims to

93
00:09:17,702 --> 00:09:23,652
find a single coherent assignment of the
highest probability, and that means that

94
00:09:23,652 --> 00:09:29,014
it is not the same as maximizing
individual marginal probabilities as we

95
00:09:29,014 --> 00:09:35,405
saw in the example. One can reformulate
this problem as one of finding the max

96
00:09:35,405 --> 00:09:41,282
over a factor product. And this is a
communitorial optimization problem which

97
00:09:41,282 --> 00:09:46,718
admits a whole range of different
solutions on which are exact and others approximate.