1
00:00:00,076 --> 00:00:06,007
Over the course of the last unit that we
have covered in the class we discussed the

2
00:00:06,007 --> 00:00:11,033
range of different inference methods, some
exact, some approximate. Sometimes solving

3
00:00:11,033 --> 00:00:16,020
the problem with marginals, sometimes for
computing MAP assignment's, and the

4
00:00:16,020 --> 00:00:21,001
question is if we're faced with a
particular task that we have to deal with

5
00:00:21,001 --> 00:00:25,076
and we have graphed a model, which
algorithm should we use? What are some of

6
00:00:25,076 --> 00:00:30,064
the choices and what guidance can we
offer about which of these methods we

7
00:00:30,064 --> 00:00:35,077
want to use. The first question we should
answer for ourselves is Which task is more

8
00:00:35,077 --> 00:00:40,004
suitable for our problem? Are we trying to
solve a problem with computing a MAP

9
00:00:40,004 --> 00:00:44,010
assignment, or are we trying to solve a
problem with computing marginals? And

10
00:00:44,010 --> 00:00:48,000
these offer sometimes non-obvious
tradeoffs, in terms of what's right for

11
00:00:48,000 --> 00:00:52,078
our application. So, computing marginals
by and large is a less fragile way to go,

12
00:00:52,078 --> 00:00:57,020
because we don't pick just a single
hypothesis. We compute a probability

13
00:00:57,020 --> 00:01:01,092
distribution over a range of different
options, and we can see for example, is

14
00:01:01,092 --> 00:01:06,095
our top option a little bit more likely
than the second best or a lot more likely

15
00:01:06,095 --> 00:01:11,048
than the second best, and that gives us
some guidance as to how robust our

16
00:01:11,048 --> 00:01:17,008
inferences are. That also gives us some
amount of confidence that we can provide

17
00:01:17,008 --> 00:01:22,051
in our answers and maybe give to the user
in guidance of how much to trust. The

18
00:01:22,051 --> 00:01:28,021
answer is produced by the system. And as
we've also seen computing probabilities is

19
00:01:28,021 --> 00:01:33,036
important for supporting the decision
making once we need to integrate the

20
00:01:33,036 --> 00:01:38,075
utility model. On the other hand MAP is
suitable in its own set of contexts. For

21
00:01:38,075 --> 00:01:44,007
example if we're trying to compute a
coherent joint assignment for example in

22
00:01:44,007 --> 00:01:49,018
the context of a speech recognition
problem or image problem and sometimes

23
00:01:49,018 --> 00:01:54,070
more important that we get something that
makes sense as a whole then we get the

24
00:01:54,070 --> 00:02:00,022
best possible answer to individual pieces
of the inference problem of individual

25
00:02:00,022 --> 00:02:05,060
pixels and phones in the way that it
doesn't makes sense in the larger problem.

26
00:02:05,060 --> 00:02:11,051
So the notion of coherence is sometimes
Important and is worth the trade off of

27
00:02:11,051 --> 00:02:17,003
reducing the robustness. We've also seen
that from computational prospective MAP

28
00:02:17,003 --> 00:02:22,040
has a range of model classes that are more
tractable then in the case of computing

29
00:02:22,040 --> 00:02:27,076
marginals so for computational reasons we
might sometimes adopt the use of a MAP

30
00:02:27,076 --> 00:02:33,000
solution just for improved efficiency.
We've also seen that especially when using

31
00:02:33,000 --> 00:02:37,033
approximate inference the MAP
assignment often provides us with

32
00:02:37,033 --> 00:02:42,037
theoretical guarantees as to how close our
answers are to the correct answers. For

33
00:02:42,037 --> 00:02:47,079
example in the context of dual competition
we've seen that. Whereas It is difficult to get a

34
00:02:47,079 --> 00:02:52,073
similar level of confidence in terms of
our, of the accuracy of approximate inference

35
00:02:52,073 --> 00:03:01,027
for computing marginals. So On the
other hand, when running approximate

36
00:03:01,027 --> 00:03:07,080
inference there are, again different
trade-offs for these two classes of

37
00:03:07,080 --> 00:03:15,013
problems. So in, when computing marginals,
one often gets for approximate algorithm

38
00:03:15,013 --> 00:03:21,069
defective errors, just by being. Soft but
just by having soft assignments errors are

39
00:03:21,069 --> 00:03:27,025
often kind of are attenuated. And the
source of inaccuracy in one part of the

40
00:03:27,025 --> 00:03:33,002
inference often doesn't make its away
significantly in other parts of the model.

41
00:03:33,002 --> 00:03:38,058
You often get more robust answers in
approximate marginals. On the other hand

42
00:03:38,058 --> 00:03:43,017
On the MAP side, one can at least gauge
in many cases at least in some algorithms

43
00:03:43,017 --> 00:03:47,070
such as Dual composition whether the
algorithm is working or not by looking at

44
00:03:47,070 --> 00:03:52,013
the value of an assignment, that we get
from the algorithm. So again, somewhat

45
00:03:52,013 --> 00:03:56,033
different trade offs. And in some
applications people actually try both and

46
00:03:56,033 --> 00:04:00,098
see which one works better in terms of the
performance in the downstream task that

47
00:04:00,098 --> 00:04:05,091
one cares about. So what are some
algorithms that we have discussed for

48
00:04:06,013 --> 00:04:12,022
doing marginal inference. So first is just
good old exact inference say [inaudible]

49
00:04:12,022 --> 00:04:19,051
and by large if problem is small enough
that exact inference fits in memory. In

50
00:04:19,051 --> 00:04:24,084
terms of the sizes of the cliques and the
subsets, it probably good to use exact

51
00:04:24,084 --> 00:04:29,094
inference. You run into less problems this
way, and if it fits in memory it's

52
00:04:29,094 --> 00:04:35,024
probably going to be very fast. If one is
not in this fortunate situation, we've

53
00:04:35,024 --> 00:04:40,095
discussed different types of algorithms
that are approximate. There's the range of

54
00:04:40,095 --> 00:04:46,046
algorithms do message passing over the
graph of which loopy message passing is

55
00:04:46,046 --> 00:04:51,083
one of the more common ones but not the
only one. And then there is the class of

56
00:04:51,083 --> 00:04:56,097
sampling methods that sample from the
distribution. And these are different

57
00:04:56,097 --> 00:05:02,089
categories of algorithms. And frankly it's
often difficult to tell in advance which

58
00:05:02,089 --> 00:05:08,046
of them is going to work better for a
given class of models. And you talk a

59
00:05:08,046 --> 00:05:14,045
little bit about factors that might favor
one of these algorithms over another in a

60
00:05:14,045 --> 00:05:20,029
subsequent slide in a couple minutes. What
about algorithms for MAP? Once again we

61
00:05:20,029 --> 00:05:26,003
have algorithms that perform in exact
inference and in this case it?s a broader

62
00:05:26,003 --> 00:05:31,083
spectrum then in the case of completing
marginals. So in addition to cases where

63
00:05:31,083 --> 00:05:37,086
we have low tree width which is category
which marginal algorithms work, we've also

64
00:05:37,086 --> 00:05:43,073
seen other examples such as those with
associative potentials And multiple, other

65
00:05:43,073 --> 00:05:49,071
cases. And, once again, if you can perform
exact inference, that's really often the

66
00:05:49,071 --> 00:05:54,097
best way to go. You're gon-, it's, it's
often going to give you the best

67
00:05:54,097 --> 00:05:59,099
performance if it's tractable. Then
there's the class of methods that are

68
00:05:59,099 --> 00:06:04,098
based on optimization. And those can be
exact methods which puts us in this

69
00:06:04,098 --> 00:06:10,036
category, but more often we're going to
find ourselves in a case where we have to

70
00:06:10,036 --> 00:06:15,074
use some kind of approximate methods, such
as a dually composition algorithm that

71
00:06:15,074 --> 00:06:20,079
we've talked about. And those methods
often as we've said lend themselves to

72
00:06:20,079 --> 00:06:25,098
some kind of, at least, being able to
estimate the performance of our algorithm

73
00:06:25,098 --> 00:06:31,058
relative to the optimal answer, even if we
can't get to the optimal answer. Finally

74
00:06:31,058 --> 00:06:38,018
there is the range of algorithms that
perform search over the space. And this

75
00:06:38,018 --> 00:06:45,090
can be simple hill climbing, search, which
is a fairly straightforward application of

76
00:06:45,090 --> 00:06:52,072
standard search methodologies but also
its. It is quite common to use some kind

77
00:06:52,072 --> 00:06:59,035
of sand plane, like the Marco [inaudible]
Monte Carlo sand plane to explore a range

78
00:06:59,035 --> 00:07:06,014
of different assignments in the space and
then select among those the ones that have

79
00:07:06,014 --> 00:07:11,082
the highest or the one that has the
highest score, yes the one with the

80
00:07:11,082 --> 00:07:17,068
highest log probability. And that is a
quite commonly used technique. It doesn't

81
00:07:17,068 --> 00:07:22,055
provide the same set of guarantees that
you might get from the optimization

82
00:07:22,055 --> 00:07:27,072
that's, as good as often, very easy to
implement, and, so is quite. Frequently

83
00:07:27,072 --> 00:07:33,028
use. So if we're resorting to the use of
approximate inference what are some of the

84
00:07:33,028 --> 00:07:38,056
issues that might make our lives more
complicated [inaudible] might favor one

85
00:07:38,056 --> 00:07:42,087
algorithm versus the other? So one
complication has to do with the

86
00:07:42,087 --> 00:07:47,097
connectivity structure; just how densely
connected. The model is. And, by and

87
00:07:47,097 --> 00:07:53,066
large, the more densely connected the
model is, the worse it is for message

88
00:07:53,066 --> 00:07:59,066
passing algorithms. So message-passing
algorithms don't like densely connected,

89
00:07:59,089 --> 00:08:05,051
models. Because the messages are
propagated over, very short cycles, and

90
00:08:05,051 --> 00:08:10,089
that can cause both issues with
convergence. As well as with ac, with lack

91
00:08:10,089 --> 00:08:16,017
of accuracy. So, lack of convergence and
lack of accuracy. Sampling methods are

92
00:08:16,017 --> 00:08:21,068
less affected by the connectivity
structure. The second, complicated factor

93
00:08:21,068 --> 00:08:27,084
is the strength of influence. That is the
extent to which nodes that are connected

94
00:08:27,084 --> 00:08:34,023
to each other have tight coupling in terms
of the preference of certain combinations

95
00:08:34,023 --> 00:08:39,079
of values. In general, the stronger the
influence the harder it is for both

96
00:08:39,079 --> 00:08:46,007
categories of, of algorithms because it
creates strong coupling. Between

97
00:08:46,007 --> 00:08:51,061
variables. Which can complicate both
message passing algorithms, as well as

98
00:08:51,061 --> 00:08:56,030
sampling algorithms, because, for example,
feeling about plain Gibb sampling, it

99
00:08:56,030 --> 00:09:01,073
makes it very difficult to move away from,
the current configuration to a different

100
00:09:01,073 --> 00:09:08,065
one. Strength of influence becomes an even
worse problem when the influences go in

101
00:09:08,065 --> 00:09:15,038
different directions. So for example, if
you have loops where one path. For, it's

102
00:09:15,038 --> 00:09:20,078
intending to make these variables take on
one configuration and a different path is

103
00:09:20,078 --> 00:09:25,074
trying to make them take on a different
combination of configurations. So for

104
00:09:25,074 --> 00:09:30,042
example as we saw in this conception
network, one path wants. A pair of

105
00:09:30,042 --> 00:09:35,052
variable to agree on their values and the
other wants them to disagree on their

106
00:09:35,052 --> 00:09:40,030
values. That really does create
significant problems for both classes of

107
00:09:40,030 --> 00:09:45,033
methods. And the reason for that, and this
I think is at the heart of what makes

108
00:09:45,033 --> 00:09:50,036
approximate inference hard, is when you
think about the shape of the likelihood

109
00:09:50,036 --> 00:09:55,039
function; if you have multiple peaks in
the likelihood function that makes life

110
00:09:55,039 --> 00:10:01,080
difficult for most approximate algorithms.
And the sharper these peaks. The more

111
00:10:01,080 --> 00:10:08,017
complicated things yet. And so that is
and, and multiple peaks are generated by

112
00:10:08,017 --> 00:10:13,086
strong influences that go in opposite
direction. And so that's really where a

113
00:10:13,086 --> 00:10:18,081
lot of the complexity in approximate
inference comes from. Okay, so now what?

114
00:10:18,081 --> 00:10:24,016
Assuming you have a model that has these
problematic these problematic issues.

115
00:10:24,016 --> 00:10:29,044
Well, so how do we address them? First is
to look at the network, and identify the

116
00:10:29,044 --> 00:10:34,033
problem regions. That is, subsets of
variables that are tightly coupled and

117
00:10:34,033 --> 00:10:39,074
maybe are subject to [inaudible] opposing
influences. And then we try and think of

118
00:10:39,074 --> 00:10:45,053
how we might make the inference in these
problem regions. More exact. So if here we

119
00:10:45,053 --> 00:10:51,052
have some tightly coupled region, with
maybe opposing influences. How do we

120
00:10:51,052 --> 00:10:56,078
Prevent our approximate inference
algorithm from. Falling into the trap, of,

121
00:10:57,015 --> 00:11:02,016
this particular area of being, giving
imprecise answers or lack of convergence.

122
00:11:02,016 --> 00:11:06,091
So for example for doing cluster graph
method we can put this entire problem

123
00:11:06,091 --> 00:11:11,024
region in the cluster. It costs us
something on the computational side

124
00:11:11,024 --> 00:11:16,006
because we have to deal with larger
clusters but it might be well worth it in

125
00:11:16,006 --> 00:11:20,084
terms of the improvement in performance.
In sampling methods we might consider

126
00:11:20,084 --> 00:11:25,001
having proposal moves over multiple
variables. So instead of sampling

127
00:11:25,001 --> 00:11:29,074
individual variables we can sample this
entire block using again some of more

128
00:11:29,074 --> 00:11:34,070
expensive sampling procedure but again
that might end up being well worthwhile in

129
00:11:34,070 --> 00:11:39,066
terms of the overall performance profile
of the algorithm. And finally if we are

130
00:11:39,066 --> 00:11:44,077
thinking about this in the context of the
[inaudible] problem, we can put this

131
00:11:44,077 --> 00:11:49,062
entire set of variable in a single slave,
which again cost us something on

132
00:11:49,062 --> 00:11:55,006
computational site but can significantly
improve the convergence profile of the

133
00:11:55,006 --> 00:12:01,036
algorithm. So really when we're faced with
a problematic model, one that doesn't

134
00:12:01,036 --> 00:12:06,051
immediately succumb to traditional
inference techniques, it turns out that

135
00:12:06,051 --> 00:12:11,086
the design of inference is often a, a bit
an art. That is, we need to study our

136
00:12:11,086 --> 00:12:17,022
model and that, think about how to deal
with different pieces of it and which

137
00:12:17,022 --> 00:12:22,085
inference method is best equipped to
handle the different pieces. And we often

138
00:12:22,085 --> 00:12:27,044
find that Complicated models, you can get
the best performance by a combination of

139
00:12:27,044 --> 00:12:31,093
different inference algorithms. Where some
pieces are handled using exact inference,

140
00:12:31,093 --> 00:12:35,067
such as these larger blocks in the
context, perhaps, of an approximate

141
00:12:35,067 --> 00:12:40,021
inference method such as sound playing or
belief propagation. And, so, one needs to

142
00:12:40,021 --> 00:12:44,022
think creatively about the inference
problem in the context of these more

143
00:12:44,022 --> 00:12:45,025
problematic models.