1
00:00:00,000 --> 00:00:05,029
We previously defined the intuition for
the dual decomposition algorithm, which

2
00:00:05,029 --> 00:00:10,038
takes an optimization objective, and
decomposes it into a bunch of different

3
00:00:10,038 --> 00:00:15,094
slaves. And uses communication between the
slaves, to try and get them to agree with

4
00:00:15,094 --> 00:00:20,062
each other about the overall, map
assignment. So now, let's take this

5
00:00:20,062 --> 00:00:26,042
intuition, and convert it into an actual
algorithm. So what we have here is, each

6
00:00:26,042 --> 00:00:33,052
slave gets its own pet objective function.
So here is the objective function for the

7
00:00:33,052 --> 00:00:40,036
I slave, for the slave corresponding to
the variable XI. And here is the objective

8
00:00:40,036 --> 00:00:47,036
function that the slave corresponding to
the larger set S, is, trying to optimize.

9
00:00:47,036 --> 00:00:54,018
Now each of these initially has as a
component its own local objective function

10
00:00:54,018 --> 00:01:01,016
that is assigned to it. But in addition
we're going to introduce for each of those

11
00:01:01,016 --> 00:01:07,082
a set of terms. These terms that modify
it's objective function, so as to try and

12
00:01:07,082 --> 00:01:14,029
get it to agree with, with the other
slaves. Specifically, we're going to try

13
00:01:14,029 --> 00:01:20,056
and get the X, the I slave, to agree with
the factors F. In which I appears, and

14
00:01:20,056 --> 00:01:28,067
conversely we're going to try and get, the
F slave to agree with the slaves of

15
00:01:28,067 --> 00:01:35,056
the variable in it's scope. So let's see
how that gets done. We are going to

16
00:01:35,056 --> 00:01:42,096
initialize all of these incentive terms,
all of these lambdas. To be zero.

17
00:01:42,096 --> 00:01:50,029
Initially, each slave makes its decision
based purely on its own local piece of the

18
00:01:50,029 --> 00:01:58,081
objective. But then, as the algorithm
evolves, these incentives start to change.

19
00:01:58,081 --> 00:02:07,081
So how does that happen? At each iteration
t, Each slave optimizes it's current

20
00:02:07,081 --> 00:02:17,016
objective. So, the I slave optimizes Theta
I hat Lamda. Where Lamda is the current

21
00:02:17,016 --> 00:02:24,090
set of penalties, the current. Set a
penalty and that gives us an assignment

22
00:02:24,090 --> 00:02:31,048
which we're going to call xi star. The f
slave does the exact same thing. It

23
00:02:31,048 --> 00:02:38,078
optimizes it's own local objective which
is [inaudible] f also, also using the same

24
00:02:38,078 --> 00:02:45,047
set of lambda and that gives it x half,
sorry, x star of f. Which is this guy over

25
00:02:45,047 --> 00:02:51,017
here. Now let's see what happens if
there's a disagreement between a large

26
00:02:51,017 --> 00:02:57,003
slave F and a variable I in it's
scope. What we would like to do, is we

27
00:02:57,003 --> 00:03:03,065
would like to incentive them to agree with
each other and so what we do is that's for

28
00:03:03,065 --> 00:03:13,056
all F. And all variables I and f, if they
disagree. That is, it's the chosen

29
00:03:13,056 --> 00:03:20,013
variable for xi in. The assignment chosen
by the factor F is different from the

30
00:03:20,013 --> 00:03:25,045
assignment I chosen by the I slave,
then we need to change their incentive

31
00:03:25,045 --> 00:03:36,029
functions and we do that. By basically
changing the, the, the lambdas. And so,

32
00:03:36,029 --> 00:03:50,070
specifically we see that, here when we
look at the penalty for the pair FI, which

33
00:03:50,070 --> 00:03:59,030
is over here, we decrease. Alpha t would
decrease by a factor alpha t which is

34
00:03:59,030 --> 00:04:08,097
greater than zero. The preference of XI
star. Which is the value chosen by, by the

35
00:04:08,097 --> 00:04:15,066
I slave. And if we see that, if we look at
that, we see that that's going to, dis-,

36
00:04:15,066 --> 00:04:22,028
disincentivize the I slave from picking
the value that it's picked. Conversely, we

37
00:04:22,028 --> 00:04:28,081
increase the preference for the v-, for
the value chosen by the F slave, which is

38
00:04:28,081 --> 00:04:34,063
this value over here. By the same amount,
alpha P. Now, that changes the preference

39
00:04:34,063 --> 00:04:40,006
of the I slave, but it also changes the
preference of the F slave by the exact

40
00:04:40,006 --> 00:04:45,001
same amounts, but in the opposite
direction. Because notice that here, we

41
00:04:45,001 --> 00:04:50,051
have a negative sign. Whereas here, we
have a positive sign. So it makes both the

42
00:04:50,051 --> 00:04:56,043
I slave and the F slave move, in the same
direction, move in opposite directions, so

43
00:04:56,043 --> 00:05:05,018
as to agree with each other. So what
happens as we continue doing these

44
00:05:05,018 --> 00:05:11,088
iterations over time? Well, one can show
that under fairly weak conditions on these

45
00:05:12,012 --> 00:05:19,006
on these parameters alpha t, the lambdas
are guaranteed to converge. What are these

46
00:05:19,006 --> 00:05:24,084
conditions? The alphas need to be big
enough. So that they make a difference. So

47
00:05:24,084 --> 00:05:30,031
that if we sum all of the alpha-T's for
alt-T, we end up with a diverging sequence

48
00:05:30,031 --> 00:05:35,046
that sums to infinity. On the other hand
they need to be small enough so that we

49
00:05:35,046 --> 00:05:40,054
eventually achieve convergence, and that
is obtained by the second condition on

50
00:05:40,054 --> 00:05:47,053
the, on the summation over here. Now, in
fact, one can also show that not only do

51
00:05:47,053 --> 00:05:54,039
we get convergence we get convergence to
unique global optimum, regardless of the

52
00:05:54,039 --> 00:06:00,039
initialization. So, the lambdas
always converge. Now, the question is

53
00:06:00,039 --> 00:06:06,091
whether the implications that, of the
convergence of the lambdas, and what

54
00:06:06,091 --> 00:06:14,002
happens at convergence. At convergence you
that there's no more change. So at that

55
00:06:14,002 --> 00:06:21,043
point each of our slaves. Has its own
locally optimal solution over its own

56
00:06:21,043 --> 00:06:34,008
variables, the ones that are in its scope.
So, is that good enough? Unfortunately not

57
00:06:34,008 --> 00:06:39,019
always. That is even though we have
achieved convergence, the solutions of

58
00:06:39,019 --> 00:06:44,073
different slaves may or may not agree on
the variables that are shared between

59
00:06:44,073 --> 00:06:50,041
them. However if they do agree, if we can
get all of the slaves to agree with each

60
00:06:50,041 --> 00:06:55,087
other, we can, we have, we can show that
the shared solution is a guaranteed MAP

61
00:06:55,087 --> 00:07:00,099
assignment. So if the slaves agree, we
have effectively solved our initial

62
00:07:00,099 --> 00:07:06,029
optimization problem, which is that
assigning a MAP assignment. If that

63
00:07:06,029 --> 00:07:12,000
doesn't happen, that is, if the slaves
have not agreed on their shared variables,

64
00:07:12,000 --> 00:07:17,084
then we need to solve what is called the
decoding problem, where, where we need to

65
00:07:17,084 --> 00:07:23,047
somehow put together these different
solutions that the different slaves have

66
00:07:23,047 --> 00:07:29,087
converged to, and come up with a single
joint assignment. So how do we do that?

67
00:07:29,087 --> 00:07:38,061
How do we solve this so-called decoding
problem? It turns out that people who

68
00:07:38,061 --> 00:07:44,064
constructed a range of different solutions
for this, none of which have particular

69
00:07:44,064 --> 00:07:50,074
strong performance guarantees, but they
often work quite well in practice. So for

70
00:07:50,074 --> 00:07:56,077
example, if we use a decomposition of the
of the original problem into spanning

71
00:07:56,077 --> 00:08:02,079
thrill. Then each of the standing trees
covers all of the variables, so we can

72
00:08:02,079 --> 00:08:09,023
take the map solution of any individual
tree and say that is an assignment to all

73
00:08:09,023 --> 00:08:15,003
of the variables. So that's one approach.
A second approach, that is not a

74
00:08:15,003 --> 00:08:21,011
one-winner takes all, is to have each of
our slaves, vote on the XI's that our in

75
00:08:21,011 --> 00:08:27,018
it's scope, and then for each XI you just
do the majority voting. So that's another

76
00:08:27,018 --> 00:08:32,080
approach. A different approach uses some
kind of weighted averaging of the sequence

77
00:08:32,080 --> 00:08:38,036
of messages that are sent, regarding each
x I through the course of the iterations

78
00:08:38,036 --> 00:08:43,064
of the algorithm. So each of these works
reasonably well but what, it turns out

79
00:08:43,064 --> 00:08:49,046
that the right solution is to simply use
multiple solutions and then pick the best

80
00:08:49,046 --> 00:08:55,092
one. And the critical observation here is
that the scoring function feta for any

81
00:08:55,092 --> 00:09:03,032
assignment. Is something that we can
easily evaluate, so why not do all of

82
00:09:03,032 --> 00:09:08,086
these? And use multiple trees and nd
generate a whole collections of Xs and

83
00:09:08,086 --> 00:09:14,061
then evaluate theta X for each of those
solutions and then pick the best one. And

84
00:09:14,061 --> 00:09:19,087
it turns out when you do that, you
generally get solutions that are better,

85
00:09:19,087 --> 00:09:25,041
in terms of their overall score, than any
fixed strategy. Now, the other nice

86
00:09:25,041 --> 00:09:31,076
aspect of this analysis. Comes back to a
point we made earlier. In this in this

87
00:09:31,076 --> 00:09:37,041
module. With, which is for every
lambda, this function that we define

88
00:09:37,041 --> 00:09:43,045
as l of Lambda. Is an upper bound on the
value of the true MAP assignment. Now

89
00:09:43,045 --> 00:09:49,040
what does that imply. It means that if you
give me any x that you think is a

90
00:09:49,040 --> 00:09:59,063
reasonable candidate. So this is a
candidate. There's a MAP assignment. Now

91
00:09:59,063 --> 00:10:04,046
by definition it is either equal to the
map or it's worse than the map. So,

92
00:10:04,046 --> 00:10:09,093
whatever the score is theta x is going to
be less than or equal to the value of the

93
00:10:09,093 --> 00:10:15,001
map assignment because it certainly can't
be any better than the maximum, true

94
00:10:15,001 --> 00:10:21,071
maximum. And that in turn is less than or
equal to L of lambda. Now the point is,

95
00:10:21,071 --> 00:10:27,054
that this is a mystery. We don't know the
value of the true MAP assignment but we

96
00:10:27,054 --> 00:10:33,060
can compute this and we can compute that.
And that gives me a bound on how bad my

97
00:10:33,060 --> 00:10:40,020
current assignment is. Because I can com-,
because I know that the difference between

98
00:10:40,020 --> 00:10:46,063
the true map assignment, and the score of
my assignment is no worse than the value

99
00:10:46,063 --> 00:10:52,052
of L lambda minus the score of my
assignment. Which mean that I can look at

100
00:10:52,052 --> 00:10:58,056
the difference between my assignment
score, and L of lambda. And if it's small

101
00:10:58,056 --> 00:11:05,086
enough, so that this is small enough. I'm
happy. Even though I might not have the

102
00:11:05,086 --> 00:11:11,036
true map assignment because I know that
I'm close enough to the point that I don't

103
00:11:11,036 --> 00:11:16,086
care anymore. And so that's a really nice
guarantee because it allows me to sort of

104
00:11:16,086 --> 00:11:22,010
stop and say, good enough. I don't know if
I'm at the optimum but where I am I'm

105
00:11:22,010 --> 00:11:28,075
happy. So what are some of the important
design choices in implementing dual

106
00:11:28,075 --> 00:11:34,067
decomposition. First there is the division
of the problem into slaves In general not

107
00:11:34,067 --> 00:11:38,095
surprisingly larger slaves that
incorporate more factors are more

108
00:11:38,095 --> 00:11:43,094
expensive to optimize. Because you're
solving a more complicated optimization

109
00:11:43,094 --> 00:11:48,093
problem within each slave. But on the
other hand they can be shown to improve

110
00:11:48,093 --> 00:11:55,004
conversion and often get you closer to the
true MAP assignment. A second design

111
00:11:55,004 --> 00:12:00,022
choice is how to select the locally
optimal solution for the slaves. In many

112
00:12:00,022 --> 00:12:05,053
cases, a slave might have more than one
optimizing assignment, and some of them

113
00:12:05,053 --> 00:12:10,084
might be more in agreement with other
slaves than, than some. And so, how do you

114
00:12:10,084 --> 00:12:16,042
pick within the set of equally good slave
assignments, the one that's going to get

115
00:12:16,042 --> 00:12:22,096
you to convergence faster? The third,
which we've briefly mentioned before, is

116
00:12:22,096 --> 00:12:28,029
how do you adjust the step size Alpha T so
as to move things towards convergence

117
00:12:28,029 --> 00:12:33,042
fast, but still slow enough to generate
convergence? There's some hard and fast

118
00:12:33,042 --> 00:12:38,061
rules that guarantee convergence but
they're often quite slow. There's cleverer

119
00:12:38,061 --> 00:12:44,014
rules that still guarantee convergence and
tend to work better in practice and this

120
00:12:44,014 --> 00:12:49,054
is an active area of research, that's
ongoing right now. And then finally we've

121
00:12:49,054 --> 00:12:54,026
talked about the decoding problem, and the
fact that there is many heuristic choices

122
00:12:54,026 --> 00:12:59,008
there, and so that's another design choice
that one needs to make when implementing

123
00:12:59,008 --> 00:13:03,084
dual decomposition. So let's summarize
different aspects of what we've talked

124
00:13:03,084 --> 00:13:08,016
about. First of all somewhere is the
algorithm. Dual composition is a

125
00:13:08,016 --> 00:13:13,006
general-purpose algorithm for MAP
inference, that works by dividing them all

126
00:13:13,006 --> 00:13:18,015
into fractable components, that could be
potentially multi, multiple factors in a

127
00:13:18,015 --> 00:13:22,086
single component, or slave. Solves each
slave locally. And then passes these

128
00:13:22,086 --> 00:13:27,093
lambda messages between them to try and
get them to agree. It, a, and, we've

129
00:13:27,093 --> 00:13:34,080
talked before about the presence of
tractable map subclasses. Any tractable

130
00:13:34,080 --> 00:13:42,069
mub sa, map subclass can be used in the
setting as a slave. Allows slaves to

131
00:13:42,069 --> 00:13:48,027
be large and richly structured as opposed
to just little tiny factors that aren't

132
00:13:48,027 --> 00:13:53,037
going to be only making very myopic
decisions based on minimal information.

133
00:13:54,037 --> 00:13:58,027
One of the nice things about the
dual composition algorithm, Is

134
00:13:58,027 --> 00:14:03,024
that it has a lot of theoretical backing
to support it. So formally, and we're not

135
00:14:03,024 --> 00:14:08,003
going to go into the details of what this
means, but just mention what this is

136
00:14:08,003 --> 00:14:12,076
actually doing from a formal perspective,
this is a sub gradient, which is kind of

137
00:14:12,076 --> 00:14:17,001
like a gradient optimization, but not
exactly. A sub gradient optimization

138
00:14:17,001 --> 00:14:21,062
algorithm on a problem that is a dual
problem, this is MAP problem, and if you

139
00:14:21,062 --> 00:14:26,053
didn't understand that, that's okay. This
is just sort of a pointer for those of you

140
00:14:26,053 --> 00:14:31,049
who might've seen some optimization before
to kind of fit this into that world. But

141
00:14:31,049 --> 00:14:37,002
this view does provide some important
guarantees, some of which I've mentioned

142
00:14:37,002 --> 00:14:43,026
in this presentation. First it gives us an
upper bound on the distance to the between

143
00:14:43,026 --> 00:14:49,022
where we are in the true MAP assignment.
And it provides us with conditions such as

144
00:14:49,022 --> 00:14:54,097
agreement among all of the slaves have
guarantee a condition under which we have

145
00:14:54,097 --> 00:15:01,003
actually found a true exact map solution.
And there's even some interesting analysis

146
00:15:01,003 --> 00:15:05,060
which I'm not going to present that tells
us when one decomposition of the model it

147
00:15:05,060 --> 00:15:09,067
displays is better than a different
decomposition of the model it displays.

148
00:15:10,000 --> 00:15:15,034
Now in practice, this algorithm has some
significant pros and cons. On the pros it

149
00:15:15,034 --> 00:15:20,043
is very general purpose. You could really
use it for any model if you just, if

150
00:15:20,043 --> 00:15:25,044
you're willing for example to decompose
this slaves fine enough. Of the

151
00:15:25,044 --> 00:15:30,071
algorithms that are currently out there,
it provides some of the best theoretical

152
00:15:30,071 --> 00:15:35,052
guarantees, in terms of convergence
properties. And because of the way that

153
00:15:35,052 --> 00:15:40,085
its structured, it can use these very fast
specialized map subroutines for solving

154
00:15:40,085 --> 00:15:45,073
large model components, like matching
problems, for example, or modular, or, or

155
00:15:45,073 --> 00:15:50,087
subsets of edges that are, that are sub
modular associative. On the other hand,

156
00:15:50,087 --> 00:15:56,023
it's really not the fastest algorithm out
there. That is, there are algorithms that,

157
00:15:56,023 --> 00:16:01,020
when they work, work considerably faster
than, than the dual decomposition

158
00:16:01,020 --> 00:16:06,037
algorithm. And more so than most, it has a
lot of tunable parameters and design

159
00:16:06,037 --> 00:16:11,086
choices, which make it a somewhat finicky
algorithm to apply in practice because one

160
00:16:11,086 --> 00:16:15,098
has to play around quite a bit in order to
get the performance.