1
00:00:00,094 --> 00:00:05,032
A very different paradigm to
inference and graphic model, is the use of

2
00:00:05,032 --> 00:00:09,070
whats called sampling or particle based
methods, in those methods rather than

3
00:00:09,070 --> 00:00:13,086
trying to manipulate the exponentially,
even infinitely large probability

4
00:00:13,086 --> 00:00:17,090
distribution as a whole we randomly
sample, instan-, instances from that

5
00:00:17,090 --> 00:00:22,079
distributions and then use those instances
as a sparse representation we can use

6
00:00:22,079 --> 00:00:27,040
those instances then to estimate various
quantities that we care about regarding

7
00:00:27,040 --> 00:00:31,039
the statistics of the overall
distribution, before we show how this is

8
00:00:31,039 --> 00:00:35,075
use in the context of graphical models, let's 
go ahead and see how it's

9
00:00:35,075 --> 00:00:41,010
applied in a simple setting. So first of
all, how do we use samples for estimating

10
00:00:41,010 --> 00:00:46,087
quantities that we care about? So, imagine
that. Somehow and we're gonna talk about

11
00:00:46,087 --> 00:00:52,043
how that might happen. Somebody gives us
or we manage to construct a dataset D

12
00:00:52,043 --> 00:00:58,042
which consists of a bunch of samples from
a distribution P. And for the moment we're

13
00:00:58,042 --> 00:01:03,070
going to assume that these samples are
what's called iid, which stands for

14
00:01:03,070 --> 00:01:14,074
independent, and identically distributed.
So that's where the "i.i.d" comes from. And

15
00:01:14,074 --> 00:01:20,084
now let's imagine that we're trying to
compute or estimate and this is all going

16
00:01:20,084 --> 00:01:26,063
to be approximate, approximate some-, a
quantity of the, of the distribution P.

17
00:01:26,063 --> 00:01:32,028
And so for the moment let's focus on
really simple case where we trying to

18
00:01:32,028 --> 00:01:38,053
figure out where these are binary valued
random variables so the distribution P

19
00:01:38,053 --> 00:01:45,067
that were sampling from is. One where the
probability that one equals one is P, and

20
00:01:45,067 --> 00:01:53,037
so think of this as tossing a coin. Now
what is a reasonable estimator for this

21
00:01:53,037 --> 00:01:59,071
parameter, P? That we're trying to
estimate. The probability that X falls

22
00:01:59,071 --> 00:02:06,018
heads. Well this is fairly a intuitive
answer here. This estimator which we are

23
00:02:06,018 --> 00:02:16,007
going to call T -sub- D, Is simply
obtained by looking at all of these

24
00:02:16,007 --> 00:02:24,052
samples that we got and counting the
fraction of one. And if you think about

25
00:02:24,052 --> 00:02:31,073
it, that's a perfectly reasonable
approximation, hm? Now more generally, for

26
00:02:31,073 --> 00:02:39,057
any distribution P, and any function F
whose statistics we're trying to estimate,

27
00:02:39,057 --> 00:02:47,081
we can approximate the expectation of the
function F relative to the distribution P,

28
00:02:47,081 --> 00:02:57,050
in terms of this weighted average of the
value F. On the sample. And this is often

29
00:02:57,050 --> 00:03:11,061
called the empirical expectation. So this
is how we might have, if we had some way,

30
00:03:11,061 --> 00:03:15,087
which we have not yet talked about of
constructing or sampling from

31
00:03:15,087 --> 00:03:20,006
distribution, how we might use those
samples for approximating various

32
00:03:20,006 --> 00:03:24,086
properties, relative to the distribution
p, whether it's a probability of an event

33
00:03:24,086 --> 00:03:29,071
or the expectation of a function and know
by the way that the expectation of the

34
00:03:29,071 --> 00:03:34,021
function subsumes the probability of an
even because you can also take the

35
00:03:34,021 --> 00:03:38,071
expectation for example an indicator
function, and that correspond directly.

36
00:03:38,071 --> 00:03:44,037
With probability. So for example this
probability can be viewed as the

37
00:03:44,037 --> 00:03:54,011
expectation relative to P of the indicator
function representing X equals one. The

38
00:03:54,011 --> 00:04:01,022
function that takes one, when x equals one
and zero otherwise. So, let's think for a

39
00:04:01,022 --> 00:04:07,073
moment, just to be concrete about how one
might go about sampling from a discrete

40
00:04:07,073 --> 00:04:15,075
distribution. So imagine that we have a
discrete random variable X that takes

41
00:04:15,075 --> 00:04:23,031
on K values, X1 up to XK, and let's assume
that each of these has the XI occurs with

42
00:04:23,031 --> 00:04:30,053
probability theta I. And so we have theta
one up to theta K. How might we go about

43
00:04:30,053 --> 00:04:36,034
using computational tools to generate
samples from this distribution? Well, most

44
00:04:36,034 --> 00:04:44,025
computers give us a random-number
generator function that generates samples

45
00:04:44,025 --> 00:04:55,008
uniformly. In the interval zero one. And
so if we wanted to convert that into

46
00:04:55,008 --> 00:05:01,084
something that samples from this discrete
distribution. The simplest way of doing

47
00:05:01,084 --> 00:05:08,035
that is to basically split up the range
and make this point say theta one, this

48
00:05:08,035 --> 00:05:18,019
point theta one plus two. theta-1, plus
theta-2, plus theta-3, and let's leave it

49
00:05:18,019 --> 00:05:26,047
at that. So four values of the random
variable. And now we toss, we use the

50
00:05:26,047 --> 00:05:32,099
random number function to sample from this
space, so let's say it comes out here and

51
00:05:32,099 --> 00:05:39,035
we basically say okay, this was the range
that corresponds to X1, X2, this is X3 and

52
00:05:39,035 --> 00:05:45,056
this is X4 and so since the point fell
here, I'm going to declare that my random

53
00:05:45,056 --> 00:05:50,089
number, that my random value is X3. I
sample again, and I sample in this, this

54
00:05:50,089 --> 00:05:56,003
point over here. I'm gonna say oh, okay,
excellent. So that's how you would use a

55
00:05:56,003 --> 00:06:01,017
random number generator to sample from a
discrete distribution, something that

56
00:06:01,017 --> 00:06:07,070
we're gonna end up using a lot later in
this lecture. [sound]. So, now that we

57
00:06:07,070 --> 00:06:13,042
know how to sample. Let's think about how
you might. What are some properties of

58
00:06:13,042 --> 00:06:19,027
sampling based estimation? And it turns
out that sampling based estimation is, has

59
00:06:19,027 --> 00:06:24,064
some, what appear to be initially some
very compelling performance guarantees.

60
00:06:24,064 --> 00:06:30,084
So, the first that I'll show is something
that is called the Hoeffding bound. And

61
00:06:30,084 --> 00:06:38,063
let's parse this horribly complicated
statement that we see over here. So, first

62
00:06:38,063 --> 00:06:46,018
of all let's go in, let's work from the
inside out. This says my estimator, which

63
00:06:46,018 --> 00:06:56,099
is Td, remember this is my estimator for
p. And this says. Is, epsilon away, is

64
00:06:56,099 --> 00:07:08,005
more than epsilon away, from P. So this
has, I am badly wrong, my estimator is not

65
00:07:08,005 --> 00:07:15,024
close to the true value which is p. Okay. I
am at least Epsilon away in one side or

66
00:07:15,024 --> 00:07:20,089
the other. Now notice that this is a
property, of the data set. The, the set of

67
00:07:20,089 --> 00:07:24,090
samples that I generated. One set of
samples is gonna give me one estimate, and

68
00:07:24,090 --> 00:07:30,009
different set of samples is going to give
me a different estimate. So that brings us

69
00:07:30,009 --> 00:07:36,019
to the next layer out, which is, this data
set is not a fixed quantity. It's sampled

70
00:07:36,019 --> 00:07:42,020
randomly from the distribution. And so, I
might get good data sets. Data sets where

71
00:07:42,020 --> 00:07:48,023
the estimator is close to P. And I might
get data sets where the estimator is far

72
00:07:48,023 --> 00:07:58,002
from P. So this says, what is the
probability. Of a bad data set. For a

73
00:07:58,002 --> 00:08:10,063
sample set. Okay. So what, so that parses
the left hand side. The right hand side is

74
00:08:10,063 --> 00:08:18,006
a bound on this probability of getting a
bad dataset, a dataset where the resulting

75
00:08:18,006 --> 00:08:24,059
estimator is highly inaccurate. So we can
see that, that probability grows

76
00:08:24,059 --> 00:08:30,086
exponentially, shrinks rather
exponentially, in the number of samples M.

77
00:08:31,095 --> 00:08:37,025
On the other hand, it also shrinks with
epsilon. So the higher, the lower the

78
00:08:37,025 --> 00:08:42,089
tolerance that we have for errors, the
higher the probability of making an error

79
00:08:42,089 --> 00:08:48,046
of that magnitude. So if we need really,
really tight bounds, then that we're not

80
00:08:48,046 --> 00:08:53,086
going to get that with very high
probability. Nevertheless, something a

81
00:08:53,086 --> 00:08:59,083
probability that shrinks exponentially
with a number of samples looks really

82
00:08:59,083 --> 00:09:06,020
good, right? The second bound that has a
very similar form is the Chernoff bound.

83
00:09:06,067 --> 00:09:14,028
And the Chernoff bound has exactly that
same composition. So here is our estimator

84
00:09:14,028 --> 00:09:22,036
again. And, here this is epsilon-away from
p. But whereas this was an additive. This

85
00:09:22,036 --> 00:09:32,028
is an additive distance. This is a
multiplicative distance. So this is p

86
00:09:32,028 --> 00:09:38,046
times one minus epsilon and is the lower
bound and p times one plus epsilon is the

87
00:09:38,046 --> 00:09:45,099
upper bound. And once again this is the
probability of getting a sample that, a

88
00:09:45,099 --> 00:09:53,019
bad sample set. And once again, we have an
exponential, we have an, a bound on the

89
00:09:53,019 --> 00:09:58,063
error, which is written over here. And
once again, the number of samples appears

90
00:09:58,063 --> 00:10:04,000
in the exponent, that makes us happy. We
have the same type of epsilon squared

91
00:10:04,000 --> 00:10:09,059
term, that shows the, the dependence on
the tolerance that's required. But here we

92
00:10:09,059 --> 00:10:15,061
have this one other term over here, which
is. The actual value P to which we're

93
00:10:15,061 --> 00:10:21,086
trying, that we're trying to estimate. So,
if we can give you a bound on the error

94
00:10:21,086 --> 00:10:28,026
that you get. The, this bound on, on how
far away you are for P. A bound on the

95
00:10:28,026 --> 00:10:34,066
tolerance epsilon, and that also
bound on the probability with which we get

96
00:10:34,066 --> 00:10:40,051
a bad sample set. We can now say, for
given tolerance that we want. I'm sorry,

97
00:10:40,051 --> 00:10:47,060
for given error probability that we want.
That is, How, if we want to guarantee that

98
00:10:47,060 --> 00:10:53,083
we're within epsilon with probability
that's greater than one minus delta we

99
00:10:53,083 --> 00:11:00,017
need this many samples. And that's fairly
straightforward algebra. You simply say,

100
00:11:00,017 --> 00:11:06,073
this is less than or delta, and then you
just take logs and move things around, and

101
00:11:06,073 --> 00:11:13,013
it all comes out to be exactly this. And
for the Chernoff bound, we have a similar

102
00:11:13,013 --> 00:11:19,077
expression. And, that gives us exactly
that same kind of bound on M as a function

103
00:11:19,077 --> 00:11:25,038
of epsilon and delta. And in this case, P
as well. So that looks great, right? We

104
00:11:25,038 --> 00:11:30,012
can give you, you give me an epsilon,
which is your error tolerance and a delta

105
00:11:30,012 --> 00:11:35,028
which is the probability with which you're
willing to take being wrong and I can say

106
00:11:35,028 --> 00:11:40,038
if you can only sample these many samples
m then I can give you those probabilistic

107
00:11:40,038 --> 00:11:45,070
guarantee. They're not deterministic but
they're a bit, pretty solid. Why is this

108
00:11:45,070 --> 00:11:50,098
not a perfect solution to our inference
problems?'Cause each of these has

109
00:11:50,098 --> 00:11:57,005
significant limitations. So, let's think
about the first, which is our additive

110
00:11:57,005 --> 00:12:03,019
bound. And let's imagine that you're going
into a doctor, and you're saying, you

111
00:12:03,019 --> 00:12:08,095
know. What is the probability that I have
some horrible disease? Well, that

112
00:12:08,095 --> 00:12:15,001
probability, hopefully for you, is still
pretty low. So maybe, if you're unlucky,

113
00:12:15,001 --> 00:12:20,095
it's, I don't know, it's 1%, 2%. Well
an additive error Epsilon on 1%. The

114
00:12:20,095 --> 00:12:27,086
[inaudible], the Epsilon that you need, to
get something that's meaningfully bounded

115
00:12:27,086 --> 00:12:34,018
when the true probability P is 1%. That
case really, really small. You can't do x1

116
00:12:34,018 --> 00:12:39,067
equals 0.01 because that could move you up
from 1% to 2%. And that's the

117
00:12:39,067 --> 00:12:45,097
factor of two increase in your probability
and that something that people really care

118
00:12:45,097 --> 00:12:51,060
about the difference between one percent
and 2%. So you need something more like

119
00:12:51,060 --> 00:12:57,038
0.0001, or may be 00001 depending on you
know, how confident you wanted to feel.

120
00:12:57,038 --> 00:13:02,011
And now this epsilon squared. Over here
we're beginning to look pretty, pretty

121
00:13:02,011 --> 00:13:06,010
scary, in terms of the number of samples
that are required in order to get a

122
00:13:06,010 --> 00:13:10,092
reasonable bound. So you might come and
say well fine, let's use the Chernoff bound,

123
00:13:10,092 --> 00:13:15,084
because that gives me relative errors on
epsilon. Right? so now if epsilon is

124
00:13:15,084 --> 00:13:21,008
sorry, sorry p. So if now p is small then
by all means I can go ahead and just you

125
00:13:21,008 --> 00:13:26,020
know have a it's a multiplicative factor
of p so I can say p plus or minus one

126
00:13:26,020 --> 00:13:31,038
percent of p. Well, unfortunately there's
no free lunch because if p is small notice

127
00:13:31,038 --> 00:13:36,025
that it appears here in the denominator
and so once again we need a number of

128
00:13:36,025 --> 00:13:41,000
samples that could potentially be quite
large when we're dealing with small

129
00:13:41,000 --> 00:13:47,050
probabilities. So the main message from
this, is that sampling-based estimation is a

130
00:13:47,050 --> 00:13:53,062
reasonable thing to do when P is not too
small? When P's not too small, this works

131
00:13:53,062 --> 00:13:59,012
fine. When P begins to get smaller. We,
this, the, the tractability of this is

132
00:13:59,012 --> 00:14:04,080
more in doubt. Now that we understand when
we might expect this to work, let's think

133
00:14:04,080 --> 00:14:10,020
about how we might apply it in the context
of Bayesian networks. So here is our

134
00:14:10,020 --> 00:14:15,080
little baby network that we've used for
the student example. And what we'd like to

135
00:14:15,080 --> 00:14:21,041
do is we'd like to generate samples from
this distribution. So this a distribution

136
00:14:21,041 --> 00:14:26,074
of, remember, P of D, I, G, S, L. And we'd
like to sample from this high dimensional

137
00:14:26,074 --> 00:14:32,070
distribution. Not that high, but still. And
the way in which this is done, is actually

138
00:14:32,070 --> 00:14:38,077
very natural. When you think about the
sort of causal intuitions or forward flow

139
00:14:38,077 --> 00:14:44,077
of a Bayesian network. We start out say,
by sampling the difficulty variable. And,

140
00:14:44,077 --> 00:14:51,023
the difficulty variable sampled from this
distribution over here which is 0.6 versus

141
00:14:51,023 --> 00:14:57,046
0.4. And so, we use the trick we showed a
couple of slides ago. And say it comes out

142
00:14:57,046 --> 00:15:04,054
d0. We then write d0 over here.
Now, I'm going to sample I, and I'm going

143
00:15:04,054 --> 00:15:12,032
to toss a coin with probability 0.7-0.3,
and say it comes out, i1. Now I get the

144
00:15:12,032 --> 00:15:18,043
sample grade. And because I previously
sampled difficulty and intelligence I know

145
00:15:18,043 --> 00:15:24,069
exactly what distribution grade needs to
be sampled from. It's the distribution i1

146
00:15:24,069 --> 00:15:30,087
d0. And, so, I now sample one of the three
values of grade from the distribution in

147
00:15:30,087 --> 00:15:39,020
this row that I've picked out in the cpd
and say it comes out g1. And I proceed to

148
00:15:39,020 --> 00:15:47,089
do the same so S is sampled from this
distribution. And say it comes out say,

149
00:15:48,022 --> 00:15:56,080
s0. And G is, sorry, L is sampled from
this distribution and say it comes out L1.

150
00:15:56,080 --> 00:16:04,050
And that's a sample. And I can do the
whole thing all over again. And, so I can

151
00:16:04,050 --> 00:16:13,002
go ahead and. Erase all of the decision
that I made before, and I can do the exact

152
00:16:13,002 --> 00:16:21,041
same thing so the blue sample might end up
for example, where d1, i1 or I'll use this

153
00:16:21,041 --> 00:16:29,032
distribution and I'm going to end up say
up g2 and I'm using this distribution,

154
00:16:29,032 --> 00:16:36,030
take this one, and I use this distribution
and I get i0. And I can use this

155
00:16:36,030 --> 00:16:41,084
procedure to generate, as many samples as
I want, using a very efficient forward

156
00:16:41,084 --> 00:16:47,073
sampling process where I sample, in what's
called topological order. Topological

157
00:16:47,073 --> 00:16:53,020
means that I start from the roots and I go
down. And I always sample parents before

158
00:16:53,020 --> 00:17:08,073
their children. And so if I want to use
this process, which is very naturally

159
00:17:08,073 --> 00:17:13,098
called forward sampling. Where we say,
want to compute, to estimate the

160
00:17:13,098 --> 00:17:19,009
probability of some assignment, little y,
to some set of query variables Y. Then

161
00:17:19,009 --> 00:17:24,026
what we're going to do is we're going to
generate a bunch of samples from that

162
00:17:24,026 --> 00:17:29,037
bayes net. As many as we think is, is
adequate. And then, if I'm interested in

163
00:17:29,037 --> 00:17:34,008
some particular event, then I simply
compute the fraction of my samples,

164
00:17:34,008 --> 00:17:41,014
fraction of samples. Where Y equals Y. And
I can use that same procedure for

165
00:17:41,014 --> 00:17:45,095
computing other expectations. So whenever,
if, if I have any other function of the

166
00:17:45,095 --> 00:17:51,013
sample, I can compute the sample, function
on that sample and then average it out in

167
00:17:51,013 --> 00:17:58,021
exactly the same way that we showed on the
first slide. And now we can go ahead and

168
00:17:58,021 --> 00:18:04,024
apply the bounds that we showed before. So
for an additive bound we have this many

169
00:18:04,024 --> 00:18:09,038
samples that we need. And for a
multiplicative bound we have this many

170
00:18:09,038 --> 00:18:15,048
samples that we need. And these are just
copying over the two bounds that we showed

171
00:18:15,048 --> 00:18:24,037
before. So, that's great. But that notice
gave me queries without evidence. And what

172
00:18:24,037 --> 00:18:31,070
do we do if we want to now ask a question,
not just about but the probability of Y

173
00:18:31,070 --> 00:18:38,021
but the probability of Y given some
evidence E = e? Well so now, it's not that

174
00:18:38,021 --> 00:18:43,038
easy to sample from a Bayesian network, if
I have evidence that's not at the root. If

175
00:18:43,038 --> 00:18:48,054
I have evidence to the roots, then that's
fine I know the value of that variable and

176
00:18:48,054 --> 00:18:53,021
I just stick that in and ignore it. You
know everything else. But if I have a

177
00:18:53,021 --> 00:18:58,025
variable where that I observed someone in
the middle, on the bottom of the network.

178
00:18:58,025 --> 00:19:03,055
Then what happens when I get there? Do I
sample it, do I ignore it? I mean it seems

179
00:19:03,055 --> 00:19:08,097
a bit unclear. And so the simple solution
that, and we'll talk about others, is an

180
00:19:08,097 --> 00:19:14,024
algorithm that's called rejection
sampling. And what it does, is it does the

181
00:19:14,024 --> 00:19:20,038
most naive thing that you could possibly
imagine. I generate samples from a Bayes

182
00:19:20,038 --> 00:19:28,075
net, and then if they don't agree with my
evidence I throw'em out. And that course.

183
00:19:28,075 --> 00:19:38,025
The remaining samples. So the remaining
sample after I throw out. All of the ones

184
00:19:38,025 --> 00:19:44,082
that are inconsistent with my evidence are
actually sampled from the conditional

185
00:19:44,082 --> 00:19:56,003
distribution. Because this is the same as
basically, reducing the distribution to

186
00:19:56,003 --> 00:20:00,057
sort of ignore the parts that are not
consistent with my evidence. So that's

187
00:20:00,057 --> 00:20:05,017
great, because now I have samples from the
right distribution. And once I have

188
00:20:05,017 --> 00:20:10,007
samples from the right distribution, I can
go ahead and compute the fraction where

189
00:20:10,007 --> 00:20:14,090
Y=little y, or, for that matter, any other
expectation that I care about. Good!

190
00:20:14,090 --> 00:20:22,028
What's the problem with this? Think about
how likely I am to keep a sample. A sample

191
00:20:22,028 --> 00:20:29,021
is going to be consistent with the
evidence with the probability which is the

192
00:20:29,021 --> 00:20:35,097
probability of the evidence. [inaudible]
that's sort of the definition. So the expected

193
00:20:35,097 --> 00:20:43,055
number, the expected fraction of samples
that I keep is exactly P(e). So now let's

194
00:20:43,055 --> 00:20:48,000
go back to, for example, a medical
diagnosis setting, or, or, for that

195
00:20:48,000 --> 00:20:53,053
matter, the, the, the message decoding
example that we talked about previously.

196
00:20:53,053 --> 00:20:58,073
How likely is your average evidence? So
let's think about medical diagnosis. A

197
00:20:58,073 --> 00:21:03,099
person comes in, and they have their age,
and their weight, and their gender, and,

198
00:21:03,099 --> 00:21:08,098
you know, 32 symptoms, and ten test
results. And, you know, the fact that they

199
00:21:09,018 --> 00:21:14,030
were, they went on a trip to Europe last
week. And all of these are pieces of

200
00:21:14,030 --> 00:21:18,063
evidence, and the question is
how likely is that configuration of

201
00:21:18,063 --> 00:21:24,039
evidence? And the answer is vanishingly
small. How likely is your random person

202
00:21:24,039 --> 00:21:31,020
off the street to exhibit this exact
combination? Almost none. And similarly with

203
00:21:31,020 --> 00:21:38,064
a message example. How likely is, are you
to get a particular configuration of noisy

204
00:21:38,064 --> 00:21:45,019
bits? Well, exponentially small also. So,
the number of samples needed grows

205
00:21:45,019 --> 00:21:50,072
(supposed to be grows) exponentially with
the number of observed variables. The more

206
00:21:50,072 --> 00:21:55,077
numbers you observe the lower the
probability of the evidence. And this is

207
00:21:55,077 --> 00:22:01,031
an exponential decay. And so that means
that, if you observe more than a couple of

208
00:22:01,031 --> 00:22:07,033
variables basically this is not a good
algorithm. So to summarize, algorithm

209
00:22:07,033 --> 00:22:12,035
produces very simple procedure. It's very
easy to generate samples for a Bayesian

210
00:22:12,035 --> 00:22:17,074
network and we showed how all these pieces
fit together. And once you've done

211
00:22:17,074 --> 00:22:22,069
that there's really elegant and
theoretically compelling epsilon-delta

212
00:22:22,069 --> 00:22:28,025
bounds as we've shown before. But their
usefulness, unfortunately is limited. The

213
00:22:28,025 --> 00:22:33,095
additive bounds tend to be useless for low
probability events. The multiplicative,

214
00:22:33,095 --> 00:22:39,087
multiplicative bounds are not good either
because the number of samples grows. As a

215
00:22:39,087 --> 00:22:44,008
function of one over the probability of
the event that we're trying to estimate.

216
00:22:44,008 --> 00:22:48,035
And all this is completely irrelevant as
soon as you have evidence because as soon

217
00:22:48,035 --> 00:22:52,035
as you have evidence the number of
required samples grows exponentially with

218
00:22:52,035 --> 00:22:56,062
the number of observed variables. Which
means this is not a feasible solution for

219
00:22:56,062 --> 00:23:01,030
most practical settings. And one final
note that's worth highlighting, this is

220
00:23:01,030 --> 00:23:06,064
the only case in, I think this, the entire
section on inference where I talked about

221
00:23:06,083 --> 00:23:12,018
Bayesian networks specifically and that is
because, because forward sampling unlike

222
00:23:12,018 --> 00:23:17,046
any of the other inference algorithms that
we are going to talk about is just not

223
00:23:17,046 --> 00:23:22,035
feasible for Markov networks because
there's no, you know, there is no notion

224
00:23:22,035 --> 00:23:28,001
of starting at the root. There is no root.
There is no sort of any variable that you

225
00:23:28,001 --> 00:23:33,046
would naturally start with whose
probability you actually know. And so we

226
00:23:33,046 --> 00:23:36,068
don't apply forward sampling to Markov
networks.