Skip to content

16 Bayes Nets Sampling

Variable Elimination ordering

  • for the query \(P(X_n | y_1 \dots y_n)\) work through the following orderings
Z -> X1 -> Y1
Z -> X2 -> Y2
...
Z -> Xn -> Yn
  • we can write out all the factors
  • we have to choose a variable that we can do our elimination on
  • we can write down all the joint distributions encoded in this Bayes net model

\(P(Z) \cdot P(X_1|Z) \cdots P(X_n|Z) \cdot P(Y_1|X_1) \cdots P(Y_n|X_n)\)

  • we start with eliminating \(X_1\)
  • so all distributions that eliminate \(X_1\) are \(P(X_1|Z)\) and \(P(Y_1|X_1)\)
  • we can then choose \(X_2\) and so on

  • it's not too bad, but we have to join just two tables

  • but let's say we want to eliminate \(Z\) first — we're going to pick out all \(N + 1\) factors: \(P(Z), P(X_1|Z), \dots\)

  • when eliminating on \(Z\), we have a much bigger table to deal with. if we choose to eliminate \(Z\) first we'd end up with a really large distribution, whereas choosing \(X_1\) and \(X_2\) first keeps the distributions small, letting us multiply and eliminate
  • choosing the correct order can be tricky, and it's hard to choose a good one, but at its worst this process is still going to be size \(2^n\), where \(n\) is the branching factor of \(Z\) when we choose to eliminate \(Z\). the worst case is the largest outgoing degree in the DAG

  • much smaller — it's \(2^n\) vs \(2^2\) if we choose poorly in this scenario

  • just so you're aware: the runtime for variable elimination on a BN is whatever the size of the largest factor is — the largest table we could have gotten. so in general this algorithm is pretty bad, but there are special cases where we can solve the BN faster

  • if we have a structure called a polytree, there will always be an efficient ordering

SAMPLING

  • we just draw \(N\) samples from some sampling distribution. ideally, if our sampling procedure is good, it should converge to the true probability. so in our Bayes nets model, we can use sampling to try to speed up the inference
  • we saw how it can be really slow, so we want to try our hand at sampling. we won't get exactly the exact answer, but the more samples we get, the better our approximation
  • instead of crunching the numbers from the table like variable elimination, we can use samples to evaluate. through a large number of samples, we can see the distribution solidify to the real answers

sampling over a given distribution

  • step 1: get a sample \(u\) from a uniform distribution over \([0, 1]\)
  • step 2: convert this sample \(u\) into an outcome for the given distribution by having each target outcome associated with a sub-interval of size equal to the probability of the outcome

Example

C P(C)
Red 0.6
Green 0.1
Blue 0.3 
red = 0.6
green = 0.1
blue = 0.3
# cumulative interval boundaries
red =>                  # Red:   [0, 0.6)
red + green =>          # Green: [0.6, 0.7)
red + green + blue =>   # Blue:  [0.7, 1.0)

prior sampling

  • lets do some bayes nets sampling
C -> R
C -> S
S -> W
R -> W

\(P(+c) = 0.5\) \(P(-c) = 0.5\)

\(P(S|C)\)

C S P
+c +s 0.1
+c -s 0.9
-c +s 0.5
-c -s 0.5

\(P(R|C)\)

  • we could easily crunch the numbers
  • the probability that you draw a specific sample is equal to the probability encoded in the Bayes net

PRIOR SAMPLING

  • we need a bit more machinery
  • if we want to know \(P(W)\)
for i = 1, 2, ..., n:
    sample xi from P(Xi | Parents(Xi))
return (x1, x2, ..., xn)

rejection sampling

  • this enables us to answer questions. before, we were only able to answer things like \(P(W)\); now we just wanted to know \(P(C)\)
  • in this case we have all the samples
  • no point in keeping all samples around
  • just tally counts of \(C\) as we go
input: evidence instantiation
for i = 1, 2, ..., n:
    sample xi from P(Xi | Parents(Xi))
    if xi not consistent with evidence:
        reject: return  -- no sample is generated in this cycle
return (x1, x2, x3, ...)

problems with rejection sampling - we now have the tools to find the conditional probability of \(W\) - say this is our Bayes net model and this is our list of samples. out of these 5 samples, only one is blue (if we're considering the blue shape). we collected the samples, and only 1 ended up being blue - with so few matching samples, our approximation of the true value probably wouldn't be good. this is a way rejection sampling goes wrong — we throw away too much. instead of waiting for the right sample, we could wait for the evidence to match

likelihood weighting

idea: fix evidence variables and sample the rest - problem: sample distribution not consistent!

shape -> color
  • pyramid, green
  • pyramid, red
  • sphere, blue
  • cube, red
  • sphere, green

consider \(P(\text{Shape} | \text{blue})\)

  • it turns out we can fix this by weighting these samples from the weird distribution by their likelihood of showing up under our original distribution. since we only see samples where the color is blue, we weight them: maybe a given sample actually isn't that likely, so we multiply by the probability it would have had if we'd sampled from our conditional distribution
  • we weight them by the probability of the evidence

what is \(P(C | +s, +w)\)? - if we have \(P(C)\), \(P(S|C)\), \(P(R|C)\), \(P(W|S, R)\) - we're not changing the tree/graph. we're told the sprinkler is on (\(+s\)) and the grass is wet (\(+w\)), so our samples will always have \(+s\) and \(+w\) because we've rigged our distribution. we weight them by the probabilities of the evidence

  • we don't have to weight \(+w\) while using it as such

  • this sample isn't from our distribution, but that's okay — we can weight it by that likelihood, which basically puts the sample back into the space without it being from the underlying distribution, and without going back to rejection sampling (where we have to throw away a lot of samples that don't match our evidence)

  • how does that look in algorithmic form? we start with our weight at \(w = 1\) because we always start at the top of the graph. then, if \(X_i\) is our evidence variable, we observe \(X_i\) and our weight becomes \(w \cdot P(X_i | \text{parents}(X_i))\)
w = 1.0
for i = 1, 2, ..., n:
    if Xi is an evidence variable:
        xi = observed value of Xi
        w = w * P(xi | Parents(Xi))
    else:
        sample xi from P(Xi | Parents(Xi))
return (x1, x2, ..., xn), w
  • all of this is to say that likelihood weighting is a consistent sampling procedure. to make rejection sampling more consistent — so we don't have to throw away so many things — we keep the samples that are consistent with our evidence. now we're cheating a little bit: we're only looking at samples consistent with the evidence. we changed the distribution, so we have to manipulate it slightly to have it match the original evidence

Example: fire alarm

  • in likelihood weighting, evidence influences the choice of downstream variables, but not upstream ones
F -> A

\(P(+f) = 0.001\) \(P(-f) = 0.999\)

\(P(+a | +f) = 0.9\) \(P(-a | +f) = 0.1\) \(P(+a | -f) = 0.01\) \(P(-a | -f) = 0.99\)

  • say we draw a set of samples, and the first node comes out \(-f\)
  • if we want to do likelihood weighting, we look at all the samples where we have \(+a\). we flip a coin and the alarm didn't go off, so we're forced to pretend the alarm went off all along and then redistribute. we use that to de-weight the sample, because that sample is unlikely to see in our model
  • we didn't account for the fact that we were told the alarm was going off when we were sampling for \(F\)

  • the evidence influences the choices of the downstream variables

  • we don't want to consider the likelihood of a downstream node given an upstream node. there's still a sampling procedure taking the evidence into account as we generate the samples, and the more samples we have the more we converge to the true probabilities. but likelihood weighting doesn't let us solve a reverse query, where we're trying to find the probability of a downstream variable given evidence on an upstream variable

  • how do we do that? Gibbs Sampling

GIBBS SAMPLING

  • it might be more helpful to walk through an example, so let's walk through an example. the basic idea is that we start as though everything is assigned, and we change things little by little until the solution we desire is found. we can do sampling on upstream vars given downstream vars, etc.

step 1: fix the evidence - \(R = +r\)

step 2: randomly initialize the other vars - \(C = +c\) - \(S = -s\) - \(W = -w\)

  • from there we can compute these conditional probabilities, so we can compute the probability of one variable given the others. we choose a variable \(X\) that is not the evidence — we could use \(S\), \(C\), \(W\) but not \(R\)
  • let's choose \(S\): what is the probability that \(S\) takes its value given the other three variables? we look at the tables and sample for the probability of \(S\) given the values of the other three
  • then we flip a coin to reassign \(S\), and we pick another variable, for example \(C\)

  • now we want to find the probability of \(C\) given everything else that we know

  • sample from \(P(S | +c, +r, -w)\)

  • sample from \(P(C | +s, -w, +r)\)

  • sample from \(P(W | +s, +c, +r)\)

  • here in Gibbs sampling, we can do whatever — we can sample according to children and parents, all the nodes. this fixes a lot more issues and can consider all of the evidence, etc.

  • we can figure out what this probability would be given what we know from our Bayes nets stuff

  • the samples we get from Gibbs sampling end up being highly correlated; each one depends on the previous values, but this is still okay, and we're still able to get consistent samples.