Sampling

Question 1

What are the two problems we often want to solve with sampling using Monte Carlo methods?

Answer 1

1. Generate samples for simulation (generative models) or represantion of distrubutions
2. Compute expectations (solve integrals), e.g. mean/variance, marginal likelihood, prediction

Question 2

How can we approximate expectation of f(x) using monte carlo?

Answer 2

Let x_s be samples, then

E(f(x)) = integ f(x)*p(x) dx = approx (1/S) sum f(x_s)

Question 3

How can we approximate predictions using monte carlo sampling?

Answer 3

Let theta_s be samples, then:
p(y|x) = integ p(y|x,theta) p(theta) d theta = approx
(1/S) sum p(y|x,theta_s)

Question 4

Is the monte carlo estimator for expectation biased?

Answer 4

No it is unbiased

Question 5

What happens to the variance of the monte carlo estimator for expectation when the number of samples, S, increases?

Answer 5

It decreases by a factor of 1/S

Question 6

How can we use monte carlo to sample discrete values?

Answer 6

Sample from U(0,1), assign the probability for different outcomes to different intervals

Question 7

What is the rejection sampling algorithm?

Answer 7

1. Assume that sampling from p(x) is difficult, but evaluating p_hat(x) = Zp(x) is easy.
2. Estimate the complex distribution p_hat(x) using a simple distrubution q(x)
3. Calculate a k such that kq(x) > p_hat(x)
4. Draw sample, x_s from q(x)
5. Draw sample u_0 from uniform = U[0, kq(x_s)]
6. Reject if u_0 > p_hat(x_s), else retain.

Question 8

What are the problems of rejection sampling?

Answer 8

1. k might be difficult to estimate

2. We might reject most samples

Question 9

What is the idea behind importance sampling?

Answer 9

Instead of throwing away samples, we weigh them by w_s = p(x_s)/q(x_s). So Ep( f(x) ) = Eq( f(x) * w_s) = approx 1/S sum f(x_s) w_s

Question 10

Is importance sampling unbiased?

Answer 10

Yes, if q > 0 when p > 0.

Question 11

What are the dissadvantages of importance sampling?

Answer 11

1. Breaks down if we do not have enough samples (puts almost all weight on a single sample)
2. Requires evaluating true p
3. Does not scale to high-dimensional problems

Question 12

What is the idea behind MCMC (Markov Chain Monte Carlo)?

Answer 12

Instead of generating independent samples, use a proposal function q that depends on the previous sample.

p(x_t+1|x_t) = T(x_t+1|x_t) where T is called a transition operator. Example:

T(x_t+1|x_t) = N(X_t+1 | x_t, sigma^2*I)

Question 13

Name a necesary property for the MCMC transition operator.

Answer 13

The markov property, so

p(x_t+1|x_t, x_t-1…. x_0) = p(x_t+1|x_t)

Question 14

What are the properties of the samples from MCMC?

Answer 14

They are not independent, but they are unbiased, so we can take the average.

Question 15

What are the four different ways a markov chain might behave?

Answer 15

1) Diverge
2) Converge to a single point
3) Conberge to a limited cycle
4) Converge to an equilibrium distribution

Question 16

What kind of behaviour do we want from our MCMC markov chain?

Answer 16

Converge to an equilibrium distribution

Question 17

How can we reduce the dependency of our samples?

Answer 17

Discard most of the samples, keeping only every M’th sample.

Question 18

What are the two conditions for converging to a equilibrium distrubution?

Answer 18

1. Invariance/ Stationarity,
   If we run the chain a long enough time, and we are in the equilibrium distribution, we stay in the equilibrium distrubution
2. Ergodicity
   Any state can be reached from anywhere.

These conditions ensure that we only have one equilibirum distribution.

Question 19

Name a sufficient condition for p* beeing invariant

Answer 19

Detailed balance, p(x)T(x’|x) = p(x’)T(x|x’)

Question 20

What is the Metropolis-Hasting algorithm?

Answer 20

Assume that p_hat = Zp can be evaluated easily.

1. Generate proposal x’ ~ q(x’|x_t)
2. If q(x_t |x’)p_hat(x’) / q(x’|x_t) p_hat(x_t) > u where u~U[0,1] accept sample, so x_t+1 = x’, else set x_t+1 = x_t

Question 21

Let q(x’|x_t)~N(x’|x_t, sigma^2) and let sigma be the step size. What happpens with

1) Large step sizes
2) Small step sizes

Answer 21

1. The method won’t work, we might reject too much

2. We might not explore enough.

Question 22

What distributions do we need for Gibbs?

Answer 22

We need the conditional distributions for each paramter.

Question 23

What is the requirement for Ergodicity (Any state can be reached from any point) in Gibbs sampling?

Answer 23

All conditionals are greater than 0.

Question 24

What are the steps for finding the conditional distribution?

Answer 24

1. Write down the log-joint distribution p(x1, x2…, xn).
   For each x_i:
2. Remove terms not dependent on x_i
3. Use the closest “known” distrubution as yours.

Question 25

Why isn’t Gibbs sampling suited for highly correlated samples?

Answer 25

Gibbs sampling can only move along the “axis” direction, this is bad for correlated distrubutions which are spread out along diagonals.

Question 26

What is block and collapsed Gibbs sampling?

Answer 26

Collapsed:
Analytically integrate out parameters
Block:
Sample groups of variables at a time.

Question 27

What are the basic steps behind slice sampling?

Answer 27

Draw u~U[0, p_hat(x_t)] ( From 0 to the maximum of the unnormalized sitribution)
Draw x_t~U[x: p_hat(x) > u] (Horizontal slice)