1
00:00:00,000 --> 00:00:04,096
We previously defined the map inference
problem, which is that of finding the,

2
00:00:05,015 --> 00:00:09,080
highest probability assignment to a
graphical model. And we talked about

3
00:00:09,080 --> 00:00:15,028
particular classes of models for which the
map problem was tractable. One was a class

4
00:00:15,028 --> 00:00:20,024
that, of models that had sufficiently low
tree width. So that one could use

5
00:00:20,024 --> 00:00:25,040
techniques such as variable elimination or
clique tree methods. And then we also

6
00:00:25,040 --> 00:00:30,023
talked about a variety of other special
purpose classes where one could do

7
00:00:30,023 --> 00:00:35,086
tractable inference. We are going to talk
about now is a general purpose algorithm

8
00:00:35,086 --> 00:00:41,003
that can be used to solve any MAP
problem, keeping in mind of course that

9
00:00:41,003 --> 00:00:46,042
the MAP problem is an NP-hard
problem, so you're not going to get a

10
00:00:46,042 --> 00:00:52,009
fully polynomial time algorithm that, that
one can utilizes in the context of any

11
00:00:52,009 --> 00:00:57,061
problem. So the class of methods that
we're going to talk about is in, is called

12
00:00:57,061 --> 00:01:03,024
Dual Decomposition. And it's derived from
the increasingly prevalent view of the MAP

13
00:01:03,024 --> 00:01:08,040
inference problem as an optimization
problem and building on techniques from

14
00:01:08,040 --> 00:01:14,032
the field of optimization theory. Let's go
ahead and first reformulate the problem in

15
00:01:14,032 --> 00:01:19,073
a way that makes it amenable to this kind
of analysis and this is just a convenience

16
00:01:19,073 --> 00:01:26,068
so here we are going to assume that the
MAP problem that we are trying to optimize

17
00:01:26,068 --> 00:01:29,096
remember we've reformulated this
as a max sum as opposed to a max product

18
00:01:29,096 --> 00:01:35,037
which is a convenient reformulation and we
are going to assume that the data that we

19
00:01:35,037 --> 00:01:41,010
are trying to optimize is comprised of a sum
of two different kinds of factors. The

20
00:01:41,010 --> 00:01:46,084
first is singleton factors. Which are over
the scope of single variable XI and the

21
00:01:46,084 --> 00:01:52,017
second are larger factors that are over
the scope of multiple variables.

22
00:01:52,017 --> 00:01:57,042
And clearly one can fold in the singleton
factors into some larger factor that

23
00:01:57,042 --> 00:02:03,023
contains a variable in its scope but it
turns out to be convenient to keep them in

24
00:02:03,023 --> 00:02:08,084
the model for reasons that will become
clear in a minute. So now our goal is to

25
00:02:08,084 --> 00:02:14,005
find the value for the moment. We're going
to talk about how to find an actual

26
00:02:14,005 --> 00:02:19,019
assignment in a little bit, but imagine
that our goal is to just figure out what

27
00:02:19,019 --> 00:02:24,040
is the value of the highest probability
assignment X. And so we're trying to find

28
00:02:24,040 --> 00:02:33,002
the X that maximizes this total summation.
One thing that we could do, which would be

29
00:02:33,002 --> 00:02:38,007
wrong, but we could do it, is to say,
well, let's forget about the fact that

30
00:02:38,007 --> 00:02:43,011
we're trying to do a single joint
assignment. Rather, we're going to think

31
00:02:43,011 --> 00:02:48,078
about each problem with blinders on. So
we're going to think about, each theta I,

32
00:02:48,078 --> 00:02:54,058
XI, by itself. And we're going to find the
XI that optimizes that, factor. And we're

33
00:02:54,058 --> 00:03:00,031
going to do the same for the larger
factors. Now, that of course is going to

34
00:03:00,031 --> 00:03:05,045
be a very poor solution because the XI
that going to optimize one data I, Is going to be

35
00:03:10,045 --> 00:03:15,059
completely inconsistent with the Xi that is selected by 
one of the larger factors that contains XI.

36
00:03:15,059 --> 00:03:22,093
So, you're going to get a completely incoherent joint
assignment. It's not going to be a joint assignment.

37
00:03:22,093 --> 00:03:26,034
It's going to be a bunch of different assignments
that don't that don't agree with each

38
00:03:26,034 --> 00:03:31,070
other. So, what dual decomposition does is
it's going to try and do the same kind of

39
00:03:31,070 --> 00:03:36,071
divide and conquer, but it's going to do
it in a way that tries to force these

40
00:03:36,071 --> 00:03:44,022
local decision-making problems to agree
with each other. And so how are we going

41
00:03:44,022 --> 00:03:48,070
to do that. We are going to do that by
introducing a set of costs. And the costs

42
00:03:48,070 --> 00:03:53,018
are going to be things that are going to
drive each of these local problems to

43
00:03:53,018 --> 00:03:58,072
hopefully, eventually agree with the
decisions made in other local problems. So

44
00:03:58,072 --> 00:04:05,019
going back to this, what we're going to
do, and now this is actually an equality.

45
00:04:06,000 --> 00:04:11,073
Is, we're going to do the following. For
the variable I, we have its own local

46
00:04:11,073 --> 00:04:17,047
potential, theta I. And then we have a
bunch of costs. And these are the costs

47
00:04:17,047 --> 00:04:23,051
that are derived from the [inaudible], and
we have a cost for each factor F that

48
00:04:23,051 --> 00:04:29,025
contains I in its scope. And that cost is
going to try and pull the little I,

49
00:04:29,048 --> 00:04:35,014
decision maker, which is called the slave,
by the way. Each of these decision

50
00:04:35,014 --> 00:04:42,093
problems is called a slave. So this is the
I slave. And here is a little term that's

51
00:04:42,093 --> 00:04:50,060
suppose to pull the i slave, to agree
with the decision made in factor f.

52
00:04:51,057 --> 00:05:03,071
Similarly, we have an F slave. And what
we're trying to do, is we're trying to get

53
00:05:03,071 --> 00:05:18,004
the F slave to agree with the i slaves.
For the variable Xi and its scope. Now, as

54
00:05:18,004 --> 00:05:24,066
written over here, let's convince
ourselves that this expression is, in

55
00:05:24,066 --> 00:05:32,005
fact, equal to the first line. And then
reason is that, here, I add a term, lambda

56
00:05:32,005 --> 00:05:39,052
FI of XI, for I in the scope of F. And
here, I subtract that same expression over

57
00:05:39,052 --> 00:05:47,028
here. So each of these expressions, lambda
FI gets added in at I, and subtracted out

58
00:05:47,028 --> 00:05:54,045
at F. And so they cancel out. So far, I've
had equality. But now, I'm going to really

59
00:05:54,045 --> 00:05:59,082
let each agent make their own decision. So
now, before, there was still the

60
00:05:59,082 --> 00:06:05,093
maximization on the outside. Now I'm going
to let each agent look at its little set

61
00:06:05,093 --> 00:06:11,089
of factors, that, it owns. Including the
sort of penalty terms that it has in, in

62
00:06:11,089 --> 00:06:17,077
order to agree with the other slaves. And
each one is going to make its separate

63
00:06:17,077 --> 00:06:25,054
optimization with all of those terms
together. So, you can think of these,

64
00:06:25,054 --> 00:06:35,098
these penalty terms as messages from, or
between, F and I. Their, their way to

65
00:06:35,098 --> 00:06:42,002
communicate. For F to communicate to I
what it thinks ought to be done and for I

66
00:06:42,002 --> 00:06:49,099
to communicate with F at the same time.
Now one important point that we'll come

67
00:06:49,099 --> 00:06:55,091
back to, in a little bit, is that this,
function here which is called L of Lambda,

68
00:06:55,091 --> 00:07:03,045
notice that this is a function of Lambda.
And only a function of lambda because it's

69
00:07:03,045 --> 00:07:09,043
no longer a function of x because of
maximize over the x. So you're going to

70
00:07:09,043 --> 00:07:15,064
get a different value of this function
depending on the choices of the penalty

71
00:07:15,064 --> 00:07:21,037
parameters. This function is an upper
bound on max theta for any value of

72
00:07:21,037 --> 00:07:27,058
lambda. Now let's understand why that is.
It's, we've seen in this line over here

73
00:07:27,058 --> 00:07:34,042
that this is actually equal to that.
Anyways, we've shown that everything

74
00:07:34,042 --> 00:07:42,020
cancels here. And what I've done here is,
over here, I'm forcing a single X to

75
00:07:42,020 --> 00:07:49,088
maximize this entire expression together.
And here, I'm letting each term be

76
00:07:49,088 --> 00:07:56,088
optimized separately. And that give me
more degrees of freedom, because here I

77
00:07:56,088 --> 00:08:03,015
have to pick the same x across the board,
and here this one gets to pick one x and

78
00:08:03,015 --> 00:08:09,019
this one get to pick another value of x.
And so since, the assignment where they

79
00:08:09,019 --> 00:08:15,054
all agree is a, is one of the assignments
that can be consider in this optimization

80
00:08:15,054 --> 00:08:22,067
problem over here. The overall value that
can be gained is only higher than if I had

81
00:08:22,067 --> 00:08:27,099
to force them all to agree which is a more
constrained optimization problem. In

82
00:08:27,099 --> 00:08:33,030
general, the more constraints I have on
the space that I'm optimizing the lower

83
00:08:33,030 --> 00:08:41,081
the value that I, the lower the value that
I can get. So introducing some notation

84
00:08:41,081 --> 00:08:48,054
which we'll use in a little, which we'll
use in the rest of this presentation,

85
00:08:48,054 --> 00:08:55,080
we're going to call the function that the
I slave is optimizing, theta I lambda. And

86
00:08:55,080 --> 00:09:04,028
the function that is being optimized by
the F slave, theta F lambda. So let's take

87
00:09:04,028 --> 00:09:10,057
an example to make this a little bit more
concrete because this was a little bit

88
00:09:10,057 --> 00:09:16,093
abstract. So let's go back to our to, to
our example of a four way loop where we

89
00:09:16,093 --> 00:09:23,006
have X1, X2, X3, and X4 and we're going to
have these four pairwise potentials

90
00:09:23,006 --> 00:09:29,066
which we're going to denote with letters
this time to disambiguate indices a little

91
00:09:29,066 --> 00:09:35,051
bit. So we have theta F of X1, X2, theta G
of X2, X3, theta H, and theta K. So, now

92
00:09:35,051 --> 00:09:41,007
how is this decomposition going to work
here? Let's assume for the moment that

93
00:09:41,007 --> 00:09:48,063
we're going to decompose this over edges.
So our factors are going to be, for

94
00:09:48,063 --> 00:09:57,052
example, the edge X1, X2. So now what is
the optimization problem that this factor

95
00:09:57,052 --> 00:10:05,016
chooses? Well it has its own potential,
say the f x1, x2, and then it's going to

96
00:10:05,016 --> 00:10:13,021
have these little costs that are going to
try and get it to agree with x1 on the,

97
00:10:13,021 --> 00:10:23,009
with the one slave on x1 and the two slave
on x2. We're similarly going to have, for

98
00:10:23,009 --> 00:10:34,086
x1x4, this is the k, so this is the f
slave. This is the k slave. And it's going

99
00:10:34,086 --> 00:10:41,038
to have its own potential, theta K. And
two penalty terms that are going to try to

100
00:10:41,038 --> 00:10:47,081
make, to make it agree with the one slave
on X1, and the four slaves on X4. And we

101
00:10:47,081 --> 00:10:54,065
similarly have exactly the same form for
the other two, slaves, the G slave and the

102
00:10:54,065 --> 00:11:01,021
H slave. In addition, we have slaves for
the individual variables, the one, two,

103
00:11:01,021 --> 00:11:06,097
three, four slaves. So here is the one
slave. And notice that the one slave has

104
00:11:06,097 --> 00:11:12,096
its own potential theta one, X1. And at
the same time, it has these two terms that

105
00:11:12,096 --> 00:11:18,080
are trying to make it agree on the one
side with F, which is over here. So this

106
00:11:18,080 --> 00:11:27,057
is because of this. And on the other side
with K, because of that. And the same

107
00:11:27,057 --> 00:11:33,066
thing applies to the other slaves, so the
two slave for example, is going to agree

108
00:11:33,066 --> 00:11:39,052
with F. And is going to try to be, is
going to be [inaudible] with F and with G,

109
00:11:39,052 --> 00:11:52,013
so it has a lambda F2 and a lambda G2. Now
I've done this in the context of a very

110
00:11:52,013 --> 00:11:58,027
simple scenario where I've broken up my
model into the factors that existed in the

111
00:11:58,027 --> 00:12:03,052
original specification. So, for example I
had factors that were pair wise

112
00:12:03,052 --> 00:12:09,029
potentials. I had a slave for each such
factor. But that doesn't have to be the

113
00:12:09,029 --> 00:12:15,044
case. [cough] In fact, the only constraint
that I need to satisfy is that I need the

114
00:12:15,044 --> 00:12:21,043
sl, to define a slave to be defined as a
subset of factors that admit a tractable

115
00:12:21,043 --> 00:12:28,035
solution. So that each one can be
optimized. Efficiently, when considered in

116
00:12:28,035 --> 00:12:35,081
isolation. So, for example if we can, if
we'll return to this network, say one

117
00:12:35,081 --> 00:12:44,017
thing we could do is, we can introduce two
larger slaves, instead of the four smaller

118
00:12:44,017 --> 00:12:52,044
FGKH slaves, which one is corresponding to
F and G together so this is the FG slave.

119
00:12:53,094 --> 00:13:03,053
And the other one, representing the k, the
KH slave. And, in this case, if we think

120
00:13:03,053 --> 00:13:08,096
about the agreement, we still have the
one, two, three, four slaves that

121
00:13:08,096 --> 00:13:15,040
represent the individual variables. And so
now we're going to have to require that

122
00:13:15,040 --> 00:13:21,085
theta F agrees with X1, with the one slave
on X1, with a two slave on X2, and with a

123
00:13:21,085 --> 00:13:27,090
three slave on X3. And so we have this
expression, which has a lambda term for

124
00:13:27,090 --> 00:13:34,078
each of those three variables. And we have
a similar term for a similar expression

125
00:13:34,078 --> 00:13:41,005
for the KH slave, where in this case, the
KH slave has to agree with the one slave

126
00:13:41,005 --> 00:13:47,056
on X1, the four slave on X4, and the three
slave on X3. If we now think about the

127
00:13:47,056 --> 00:13:53,082
singleton slaves, for example X1, we see
that X1 has to agree with the FG slave, so

128
00:13:53,082 --> 00:14:00,030
there's a term to encourage that, and with
the KH slave because it's present in both.

129
00:14:00,030 --> 00:14:06,048
On the other hand, the X2 variable only
occurs in the first slave and so it only

130
00:14:06,048 --> 00:14:16,092
has a single agreement term with the FG
slave. And similarly for x3 and x4. So,

131
00:14:16,092 --> 00:14:22,026
how do we then construct the slaves? In
pair wise networks, what we typically do

132
00:14:22,026 --> 00:14:27,081
is we divide the factors into a set of
disjoint trees. And this is in fact what I

133
00:14:27,081 --> 00:14:33,022
showed in the previous slide. We divided
it into one tree that went through the

134
00:14:33,022 --> 00:14:38,088
first wedges, and a second one that went
through the second wedges. And then, and

135
00:14:38,088 --> 00:14:43,022
these, and they are destroying such means
as every edge is assigned to exactly one

136
00:14:43,022 --> 00:14:47,018
tree. And because they're trees we know
how to optimize in efficiency using

137
00:14:47,018 --> 00:14:51,043
[inaudible], [inaudible], [inaudible]
variation or [inaudible] tree. But we also

138
00:14:51,043 --> 00:14:56,025
discuss that there is other classes of
factors that are, that offer tractable

139
00:14:56,025 --> 00:15:00,076
inference. So for example, we talked about
matching, or models that are

140
00:15:00,076 --> 00:15:06,008
associative, or regular, or super modular,
or whatever we call them. And all of these

141
00:15:06,008 --> 00:15:11,009
are tractable classes we can take a whole
bunch of factors that satis, that, that

142
00:15:11,009 --> 00:15:16,035
fit into one of these tractable categories
and optimize them together in one svelte

143
00:15:16,035 --> 00:15:20,078
swoop. We don't need to divide into
separate edges. So let's look at an

144
00:15:20,078 --> 00:15:25,071
example of this. Remember a while ago, we
talked about the problem of 3D cell

145
00:15:25,071 --> 00:15:30,090
reconstruction, where we have a, a cell
over here that we're imaging. And we're

146
00:15:30,090 --> 00:15:36,049
taking various images that are slices, two
dimensional slices through that cell. And

147
00:15:36,049 --> 00:15:42,032
we'd like to reconstruct three dimensional
structure. So here as, as we discussed, we

148
00:15:42,032 --> 00:15:47,078
have the slices and we would like to
correspond the beads, that we see, this

149
00:15:47,078 --> 00:15:53,066
little gold beads that we see and these
different images to each other. So try to

150
00:15:53,066 --> 00:15:59,063
figure out that this bead corresponds to
the bead over there. And from that we can,

151
00:15:59,063 --> 00:16:06,047
then subsequently. Obtain the 3D
reconstruction. Now when we last talked

152
00:16:06,047 --> 00:16:12,082
about this we described this as a matching
problem, where the matching waits between

153
00:16:12,082 --> 00:16:18,084
a point here and the point here. Are
derived from the similarity of both the

154
00:16:18,084 --> 00:16:23,088
location and the 2D slice, and the
appearance of the local neighborhood. But

155
00:16:23,088 --> 00:16:28,092
it turns out that neither of these is
sufficiently distinctive in order to

156
00:16:28,092 --> 00:16:34,050
really make that determination robustly
that one point in an image matches another

157
00:16:34,050 --> 00:16:39,095
point in the other image. And so in order
to do this with a reasonable success we

158
00:16:39,095 --> 00:16:45,017
need to have another set of potentials
which are pair wise potentials. Which

159
00:16:45,017 --> 00:16:52,007
basically preserved distances of these
marker positions. So tell us that if we

160
00:16:52,007 --> 00:16:59,006
had, if we want to correspond this point
over here to this point, and this point to

161
00:16:59,006 --> 00:17:05,032
that point, then the distances between
them. Should also roughly be preserved.

162
00:17:05,032 --> 00:17:11,056
Now, this set of potentials is relatively
sparse and therefore can be solved usually

163
00:17:11,056 --> 00:17:17,027
using exact difference, this set of
potentials is not complicated on its own,

164
00:17:17,027 --> 00:17:22,091
cause it's a matching problem. If you put
them together it turns out to be a

165
00:17:22,091 --> 00:17:28,091
difficult problem to solve. In fact you
could show that a joint set of potentials

166
00:17:28,091 --> 00:17:34,055
like this, with these two different
categories is in general [inaudible] but

167
00:17:34,055 --> 00:17:41,015
using dual decomposition we can solve each
of these separately. And then communicate

168
00:17:41,015 --> 00:17:46,021
information between them. So each of these
would form a tractable slave.