1
00:00:00,000 --> 00:00:04,428
One of the reasons for the increasing
popularity of map inference, is that there

2
00:00:04,428 --> 00:00:08,749
is a large subclass of map problems that
actually allow tractable inference. Now,

3
00:00:08,749 --> 00:00:12,907
we've already seen one class of map
problems that allows tractable inference,

4
00:00:12,907 --> 00:00:17,228
which is graphical models that have
little tree width, for which you can apply

5
00:00:17,228 --> 00:00:21,602
variable elimination or clique trees. But
it turns out that, besides that, there is

6
00:00:21,602 --> 00:00:25,653
actually a rich set of other subclasses
that can be solved using efficient

7
00:00:25,653 --> 00:00:29,865
algorithms, often based on ideas from
computer science theory. So let's look at

8
00:00:29,865 --> 00:00:33,931
some of these examples, and see how we
might go about solving them. One such

9
00:00:33,931 --> 00:00:38,055
important class of problems is that of
correspondence, or data association

10
00:00:38,055 --> 00:00:42,512
problems. Here, we have two classes of
objects. In this case, the, red objects on

11
00:00:42,512 --> 00:00:46,469
the one side, and the blue objects on the
other. And we'd like to find a

12
00:00:46,469 --> 00:00:50,648
correspondence, or matching between them.
And the fact that it's a

13
00:00:50,648 --> 00:00:54,883
matching means that each, that the
assignment has to be one to one. So you

14
00:00:54,883 --> 00:01:00,048
can't have a single red dot match more
than one blue dot, or vice versa. So here,

15
00:01:00,048 --> 00:01:08,452
for example, is one. Such matching. And we
may, in addition, require that all the red

16
00:01:08,452 --> 00:01:13,872
dots be matched, or that all the blue dots
be matched, which can't be done in this

17
00:01:13,872 --> 00:01:18,891
case. So what is the quality of a
matching, given the, the set of possible

18
00:01:18,891 --> 00:01:24,245
matchings? So how do we select between
them? So, we have in the model, a notion

19
00:01:24,245 --> 00:01:29,666
of the quality of the match between I and
J, which we denote, in this case, as the

20
00:01:29,666 --> 00:01:34,819
parameter theta IJ. And so our goal in
this, in this problem, is to find the

21
00:01:34,819 --> 00:01:41,519
highest scoring matching, where the score
is defined as. The sum of. The matches

22
00:01:41,519 --> 00:01:48,991
multiplied by the quality of their score.
And we constrain the variables, X, I, J,

23
00:01:48,991 --> 00:01:56,846
these binary variables indicate whether I
is mapped to J, via the mutual exclusion

24
00:01:56,846 --> 00:02:03,040
constraint. That, that we discussed
earlier. Now, this type of problem is

25
00:02:03,040 --> 00:02:07,444
easily solved using bipartite matching
problems developed in computer science

26
00:02:07,444 --> 00:02:12,305
theory. And it turns out that, in the
context of graphical models, or

27
00:02:12,305 --> 00:02:16,856
probabilistic inference, this type of
problem has numerous applications. So, for

28
00:02:16,856 --> 00:02:21,465
example, we might have, on the one hand,
say, the, the red side, a set of sensor

29
00:02:21,465 --> 00:02:26,311
readings from a number of, say, airplanes
that we're trying to keep track of. And on

30
00:02:26,311 --> 00:02:30,743
the blue side, we might have a sen, a set
of airplanes or objects that we've

31
00:02:30,743 --> 00:02:34,821
previously detected. And we'd like to
figure out which sensor reading

32
00:02:34,821 --> 00:02:39,667
corresponds to which object. Or we might
have features in two unrelated images. And

33
00:02:39,667 --> 00:02:45,734
we'd like to figure out, which feature in
image one matches which feature in Image

34
00:02:45,734 --> 00:02:50,389
two. Or if we're trying to do doing some
kind of text analysis, we might have a set

35
00:02:50,389 --> 00:02:54,634
of entities, say people, or organizations
that we're trying to reason about, or

36
00:02:54,634 --> 00:02:58,934
learn something about. And we're trying to
match mentions in the text to those

37
00:02:58,934 --> 00:03:03,344
entities, subject to the constraint that
each mention corresponds to exactly one

38
00:03:03,344 --> 00:03:08,305
entity. So let's look at one example
application of this which corresponds to

39
00:03:08,305 --> 00:03:13,508
one of the examples that we showed on the,
mentioned on the previous slide which is

40
00:03:13,508 --> 00:03:18,710
that of 3-D cell reconstruction. In this
case we have over here a, a cell that we

41
00:03:18,710 --> 00:03:23,788
are trying to assess the 3-D structure of.
And we're looking at various slices

42
00:03:23,788 --> 00:03:28,740
through that cell taken from different
angles by a microscope. And so these are

43
00:03:28,740 --> 00:03:34,068
various two dimensional projections of the
3-D object, and we're trying to figure out

44
00:03:34,068 --> 00:03:39,119
from that three dimensional structure. Now
within the cell, we might have these

45
00:03:39,119 --> 00:03:44,858
little tiny gold beads that are that were
put into the cell so that we can somehow

46
00:03:44,858 --> 00:03:49,796
register the different images of the cell
to each other. So, here, these are

47
00:03:49,796 --> 00:03:54,935
examples of two such real images, and
these are the little gold beads, you can

48
00:03:54,935 --> 00:03:59,940
see them in, in the little circles, and
what we'd like to do, is we'd like to.

49
00:03:59,940 --> 00:04:05,341
Decide that this bead over here is the same
as that bead over there. And once we have

50
00:04:05,341 --> 00:04:10,157
that correspondence, we can then; compute
the 3D re-construction using some

51
00:04:10,352 --> 00:04:15,939
volumetric reconstruction algorithms. And in
this case, the matching weights, those

52
00:04:15,939 --> 00:04:21,354
theta IJs that we saw on the previous
slide, c-, represent the similarity

53
00:04:21,354 --> 00:04:27,371
between this position, between this dot
and this dot, in terms of the location in

54
00:04:27,371 --> 00:04:32,410
the image. And in terms of the
neighborhood appearance in, in the

55
00:04:32,410 --> 00:04:38,160
vicinity of that point. A very different
application for what is effectively the

56
00:04:38,160 --> 00:04:43,733
same kind of idea is this we have, say a 3D
mesh scan of a, of an object, such as a

57
00:04:43,733 --> 00:04:49,588
human being and we'd like to figure out
how point on this mesh match up to points

58
00:04:49,588 --> 00:04:55,231
on a somewhat related but different mesh
whether it's different pose or different

59
00:04:55,231 --> 00:05:00,945
shape. So here we would like to realize
that this point over here matches to this

60
00:05:00,945 --> 00:05:06,800
point over here or that this point on this
mesh maps to this point on this mesh.

61
00:05:06,800 --> 00:05:13,458
And once again these matching weights the
theta ij represent exactly the similarity of

62
00:05:13,458 --> 00:05:19,093
both location and again the local
neighborhood appearance. Another very commonly

63
00:05:19,093 --> 00:05:24,436
used class of tractable map sub problems
are those that involve what are called

64
00:05:24,436 --> 00:05:28,997
associative potentials. Associate, also
called regular in some cases or

65
00:05:28,997 --> 00:05:34,340
attractive, are cases where the variables
that are connected to each other like to

66
00:05:34,340 --> 00:05:39,357
take the same values. So let's consider
this example in the context of binary

67
00:05:39,357 --> 00:05:45,381
valued random variables where we have
variable XI. And the variable xj that are

68
00:05:45,381 --> 00:05:54,161
connected to each other and we have the on
diagonal potentials. The 0,0 and the 1,1.

69
00:05:54,161 --> 00:05:59,851
Which are the cases where assign XJ take
the same value and we have the off

70
00:05:59,851 --> 00:06:05,841
diagonal potentials 0,1 1,0. Where the
variables take on different values. And

71
00:06:05,841 --> 00:06:11,681
what we would like in the associated model
is for the 0,0 and 1,1 cases to be

72
00:06:11,681 --> 00:06:18,045
preferred over the off diagonal cases. And
that can be formulated using the following

73
00:06:18,045 --> 00:06:24,177
constraint in which we have that A. Plus
d, which are the on-diagonal entries, are

74
00:06:24,177 --> 00:06:29,657
at, in sum, greater than or equal to B +
C, so that in aggregate, we prefer the

75
00:06:29,657 --> 00:06:37,693
on-diagonal to the off-diagonal entries.
It turns out that. If you have even an

76
00:06:37,693 --> 00:06:43,447
arbitrary network, in terms of fully dense
connectivity, over binary variables, that

77
00:06:43,447 --> 00:06:48,569
use only the singleton potentials, and
these pair wise potentials that are

78
00:06:48,569 --> 00:06:53,972
associative. They're also called super
modular, which is a term that comes from

79
00:06:53,972 --> 00:06:59,866
mathematics. If the pair wise potential
satisfied this constraint that we saw over

80
00:06:59,866 --> 00:07:05,480
here, then you can find an exact solution,
regardless of the network connectivity.

81
00:07:05,480 --> 00:07:11,121
And that can be done using algorithms from
combinatorial optimization from computer

82
00:07:11,121 --> 00:07:16,426
science theory for finding minimum cuts in
graphs. For non-binary valued random

83
00:07:16,426 --> 00:07:22,000
variables exact solutions are no longer
possible but it turns out that very simple

84
00:07:22,000 --> 00:07:27,442
heuristics can get very, very high quality
answers very efficiently. And so many

85
00:07:27,442 --> 00:07:32,658
related variants that are not necessarily
binary admit either exact or approximate

86
00:07:32,658 --> 00:07:37,371
solutions and specifically we talked
before about the class of metric MRFs

87
00:07:37,371 --> 00:07:42,398
which occur a lot in computer vision as
well as other applications, and it turns

88
00:07:42,398 --> 00:07:47,363
out that for metric MRFs even over
non-binary variables, you can, you can use

89
00:07:47,363 --> 00:07:52,327
these very efficient algorithms. So one
such example is in the context of depth

90
00:07:52,327 --> 00:07:58,105
reconstruction. Where we have two views of
the same object taken from slight

91
00:07:58,105 --> 00:08:03,620
disparities, say, using an a, using a
stereo camera. So here is view one and

92
00:08:03,620 --> 00:08:09,663
view two in the same scene, and you can
see that they're slightly different from

93
00:08:09,663 --> 00:08:16,262
each other. And, and if we can and we now
have, for a given er, we're trying to infer

94
00:08:16,262 --> 00:08:22,200
the following image that tells us for each
pixel in the image what is the actual

95
00:08:22,200 --> 00:08:28,511
depth. That is the Z dimension. And, one
of the constraints that we'd like to

96
00:08:28,511 --> 00:08:34,763
enforce is that the because of smoothness
in the image, the z value for a pixel is

97
00:08:34,763 --> 00:08:40,482
similar to the z value of an adjacent
pixel. And that allows us to clean up a

98
00:08:40,482 --> 00:08:46,506
lot of noise that might arise if we just
try to infer the depth of individual

99
00:08:46,506 --> 00:08:53,273
pixels by themselves. And there are many other such
examples in computer vision that are used

100
00:08:53,273 --> 00:08:59,595
quite commonly and use this kind of
associative potentials. Examples include,

101
00:08:59,595 --> 00:09:05,605
for example, denoising of images
infilling of missing regions, and a whole

102
00:09:05,605 --> 00:09:11,771
variety of other tasks, including
foreground and background segmentation and

103
00:09:11,771 --> 00:09:18,905
so on. Another kind of factor that admits
efficient solutions is the cardinality

104
00:09:18,905 --> 00:09:24,790
factor and this is a factor that in
general can involve arbitrarily many

105
00:09:24,790 --> 00:09:31,078
binary variables x1 of the xk. But we are
going to require that this, that it's

106
00:09:31,078 --> 00:09:37,769
sparsely representable in the sense that
the score for an assignment the x1 of the

107
00:09:37,769 --> 00:09:44,117
xk is a function of how many x I's are
turned on. So the taken example, here is a

108
00:09:44,117 --> 00:09:49,764
factor like this over A, B, C and D, and
you can see that we have only five

109
00:09:49,764 --> 00:09:55,797
different values for entries in this
factor, we have this pink entry over here

110
00:09:55,797 --> 00:10:01,752
when the sum of the XI is zero, we have
this blue entry over here, that occurs

111
00:10:01,752 --> 00:10:07,502
when the sum of the entries is one. For
these four entries. You have the purple

112
00:10:07,502 --> 00:10:11,854
one that occurs when we have two
Xi's on; the green occurs when we

113
00:10:11,854 --> 00:10:16,443
have three and dark blue appears when we
have four. Okay, so there's only five

114
00:10:16,443 --> 00:10:21,152
different possible values here even though
there's potentially two to the four

115
00:10:21,152 --> 00:10:25,857
different possible combination. And it
turns out that this actually occurs in

116
00:10:25,857 --> 00:10:30,890
quite a number of different applications.
When we talked about parity constraints,

117
00:10:30,890 --> 00:10:35,923
for example, in message decoding. Parity
constraints are something that only looks

118
00:10:35,923 --> 00:10:40,893
at the number of XIs that are on. If you
want to have digital image segmentation,

119
00:10:40,893 --> 00:10:45,615
and you want to have some kinds of prior
on the number of pixels in a given

120
00:10:45,615 --> 00:10:50,461
category. You want to say that, in this
image, we expect the number of pixels to

121
00:10:50,461 --> 00:10:55,026
be between, you know, that are labeled sky
to be between 30 and 70%. This is

122
00:10:55,026 --> 00:11:01,212
potentially a factor over all pixels in
the image. But it, but it only counts the

123
00:11:01,212 --> 00:11:07,654
total number of pixels. And so again,
turns out to be efficient. [inaudible] And

124
00:11:07,654 --> 00:11:14,181
there's many other examples as well. A
different one that also turns out to be

125
00:11:14,181 --> 00:11:20,546
very useful in practice is the notion of
sparse of sparse patterns. So, here again

126
00:11:20,546 --> 00:11:25,744
you can have an arbitrary number of
variables x-1 up to x-k. But you only

127
00:11:25,744 --> 00:11:31,298
specify a score for some small number of
assignments. So, here for example is a

128
00:11:31,298 --> 00:11:36,638
factor again over a, b, c, and d. And I
have now only three factors, only three

129
00:11:36,638 --> 00:11:41,978
entries in that factor that get some
value. They don't have to get the same

130
00:11:41,978 --> 00:11:47,746
value but only they get some value. And
all of the ones that are white are all

131
00:11:47,746 --> 00:11:55,877
have exactly the same score. Generally
zero. And. This is actually surprisingly

132
00:11:55,877 --> 00:12:00,585
useful in practice because it's very
useful to give a higher score to

133
00:12:00,585 --> 00:12:05,965
combinations that occur in real data. So
for example, if we were doing a spelling

134
00:12:05,965 --> 00:12:10,336
problem you want to give a higher
probability to whatever letter

135
00:12:10,336 --> 00:12:15,143
combinations occur in a dictionary. And
that's a finite number. It's bounded by

136
00:12:15,143 --> 00:12:19,481
the size of the dictionary and now you
have all the combinatorially many letter

137
00:12:19,481 --> 00:12:23,818
combinations that don't occur in the
dictionary. You don't need to give them

138
00:12:23,818 --> 00:12:28,540
all a separate weight and now it turns out
to be, again, a sparse factor. The same

139
00:12:28,540 --> 00:12:34,280
thing actually occurs in an, in image
analysis problems, where for example, you

140
00:12:34,280 --> 00:12:39,796
can look all the five by five image
patches that actually occur in natural

141
00:12:39,796 --> 00:12:45,611
images that actually surprisingly small
set of patches relative to all possible 25

142
00:12:45,834 --> 00:12:51,500
pixels combinations. And so once again,
this is very commonly used factor over.

143
00:12:51,828 --> 00:13:00,189
That, that arises in practice. A different
factor that has tractable properties is a

144
00:13:00,189 --> 00:13:05,739
convexity factor. Here we have
[inaudible]. One of the XK that are

145
00:13:05,739 --> 00:13:13,245
denoted by these blue dots over here. And,
and, but now they're ordered. So this is

146
00:13:13,245 --> 00:13:19,394
X1, X2 and XK. And the convexity
constraint says, you can assign these

147
00:13:19,394 --> 00:13:26,810
vale, values, these variables one or zero,
but you have to assign them in a way that.

148
00:13:26,810 --> 00:13:32,358
Only a convex set, is assigned the value
one. So, for example, you can have this

149
00:13:32,358 --> 00:13:37,763
set be one and everything else be zero or
you can have this set be one and

150
00:13:37,763 --> 00:13:43,528
everything else be zero but you cannot
sort of have a scattered set of 1's that

151
00:13:43,528 --> 00:13:49,217
are interspersed with the 0's. And again,
this occurs in a surprising number of

152
00:13:49,217 --> 00:13:55,169
applications. You can look at parts in an
image segmentation problem and say that

153
00:13:55,169 --> 00:14:00,731
the parts should be convex. You can
think about word labeling in texts, and

154
00:14:00,731 --> 00:14:07,093
say that the words labeled with a certain,
part of speech, or a certain, a certain

155
00:14:07,093 --> 00:14:12,526
segment that corresponds to a part in the
parse tree, for example, need to be

156
00:14:12,526 --> 00:14:18,316
contiguous in the sequence. If you're
trying to label a video with a bunch of

157
00:14:18,316 --> 00:14:23,677
sub-activities, you can say that each
sub-activity needs to have a, a coherent

158
00:14:23,677 --> 00:14:29,324
span, with a beginning and end, for
example. So to summarize, there's many

159
00:14:29,324 --> 00:14:34,878
specialized models that admit a map
solution using tractable algorithm and a

160
00:14:34,878 --> 00:14:40,788
surprising number of those do not actually
have tractable algorithms for computing

161
00:14:40,788 --> 00:14:46,094
marginals. And these specialized models
are useful, in many cases, on their own,

162
00:14:46,300 --> 00:14:51,855
like the matching problem that I showed.
But also, as, we'll see in the, in, as

163
00:14:51,855 --> 00:14:57,616
we'll see as a component in a larger model
with other types of factors. And the fact

164
00:14:57,616 --> 00:15:03,171
that this, as a sub-model, has a tractable
solution, will turn out to be very useful

165
00:15:03,171 --> 00:15:03,720
as well.