We sample from Q using standard methods, similar to sampling from a linear-chain CRF by running the backward algorithm followed by forward sampling.
we run the sum-product algorithm from the leaves up to the root ♦, at each node x computing the following for each topic z: Then we sample from the root down to the leaves, first sampling ♦.z from β ♦ , then at each x = ♦ sampling the topic x.z to be z with probability proportional to Again we use IMH to correct for the bias in Q: we accept the resulting proposalẑ with probability While Pr(p, i,ẑ, x | θ, φ) might seem slow to compute because it contains many factors (1) with different denominators Z(x), one can share work by visiting the mentions x in their order i.