Concept map / MCMC

Share

Markov chain Monte Carlo

Follow a Metropolis sampler on a two-parameter item posterior and compare the resulting samples with the target distribution.

Prerequisites Bayes

1A walker on a two-parameter hill

Thirty simulated people with known abilities answer one item. The posterior for the item’s two parameters, difficulty b and discrimination a, is a hill over the (b, a) plane, and its height is the relative posterior density. With two parameters a grid can map the hill. With hundreds it cannot.

Markov chain Monte Carlo (MCMC) sends a walker over the hill instead. Each step proposes a nearby spot and either moves there or stays. Run long enough, the walker’s footprints pile up in proportion to the height.

2What to do with a downhill proposal

Seen from above, the hill is the green patch and the walker is the blue dot, starting in a corner. At each step a random nearby spot is proposed. If the proposal is higher, the walker moves there. The question is what to do when the proposal is lower. We want the walker's footprints, taken together, to show the shape of the whole hill. Which rule does that?

3Walk the hill step by step

A solid blue line marks an accepted proposal and a dashed orange line a rejected one. Take a few single steps, then run the chain at different step sizes.

Drag the picture to rotate it.

The blue dot is the walker. It starts in a far corner, where the surface is almost flat. Take one step to see a proposal.

More controls

4Do the footprints match the posterior?

Every state counts as a draw, including the repeats after a rejection. Given enough steps, the histograms of the draws settle onto the posterior's own curves, which here come from adding up the surface on a grid.

Sampled difficulty b−2.000.252.50Sampled discrimination a0.201.703.20
Where the walker has beenPosterior from the grid

No samples yet. Run the walker above.

5Only the ratio of heights matters

The chance of accepting depends on the proposed height divided by the current one. The posterior's normalizing constant is the same at both points, so it cancels, and the sampler never needs it.

chance of accepting  =  min⁡ ⁣(1,  height at the proposalheight where you stand)\text{chance of accepting} \;=\; \min\!\left(1,\; \frac{\htmlClass{term-new}{\text{height at the proposal}}}{\htmlClass{term-cur}{\text{height where you stand}}}\right)
chance of accepting=min⁡ ⁣(1,  height at the proposalheight where you stand)\begin{aligned} &\text{chance of accepting} \\ &\quad= \min\!\left(1,\; \frac{\htmlClass{term-new}{\text{height at the proposal}}}{\htmlClass{term-cur}{\text{height where you stand}}}\right) \end{aligned}

Point at a part of the fraction to find it on the hill. Take a step above to see it with numbers.

6Check yourself

The tasks use the lab in section 3, with the rule left at Accept downhill sometimes.

  • Tune the step size so that, over at least 500 steps, between 25% and 50% of proposals are accepted.Now: 0 steps, 0% accepted
  • Make the walker stick: choose a step size so large that fewer than 8% of proposals are accepted over at least 200 steps. Then look at the trace in section 4.Now: Step size 0.10, 0% accepted
  • Run long enough that the sample averages land within 0.05 of the grid values for both b and a.Now: No samples yet

7The same sampler in R

The snippet runs the same sampler on the same 30 answers, priors and starting corner, with the lab’s default step size of 0.1. About 87% of proposals are accepted, and after warmup the means of b and a, 0.02 and 1.03, are within 0.05 of the grid values the lab reports.

Run a Metropolis sampler on the item posteriorShow the code
# 30 examinees of known ability and their answers to one item
theta <- seq(-2.5, 2.5, length.out = 30)
u <- utf8ToInt("100000000001001110101011111111") - 48
# Log posterior for difficulty b and discrimination a, with
# b ~ normal(0, 2) and a ~ lognormal(0, 0.8), inside the box
log_post <- function(x) {
  b <- x[1]; a <- x[2]
  if (b < -2 || b > 2.5 || a < 0.2 || a > 3.2) return(-Inf)
  sum(dbinom(u, 1, plogis(a * (theta - b)), log = TRUE)) +
    dnorm(b, 0, 2, log = TRUE) + dlnorm(a, 0, 0.8, log = TRUE)
}

# Metropolis with a symmetric normal proposal, step size 0.1,
# starting from the page's corner at b = -1.6, a = 2.9
set.seed(1)
draws <- matrix(NA, 20000, 2)
cur <- c(-1.6, 2.9)
for (i in 1:20000) {
  prop <- cur + rnorm(2, 0, 0.1)
  ratio <- exp(log_post(prop) - log_post(cur))
  if (runif(1) < ratio) cur <- prop
  draws[i, ] <- cur
}
# Share of proposals accepted, then the means of b and a
# after 1,000 warmup draws
round(mean(diff(draws[, 1]) != 0), 2)
round(colMeans(draws[-(1:1000), ]), 2)

Uses base R only.

What the sampler relies on