I'm doing some reading on topic modeling (with Latent Dirichlet Allocation) which makes use of Gibbs sampling. As a newbie in statistics -- well, I know things like binomials, multinomials, priors etc -- I find it difficult to grasp how Gibbs sampling works. Can someone please explain it in simple English and/or using simple examples? (If you are not familiar with topic modeling, any examples will do.) Thank you all in advance.
You are a dungeonmaster hosting Dungeons and Dragons and a player casts 'Spell of Eldritch Chaotic Weather (SECW). You've never heard of this spell before, but it turns out it is quite involved. The player hands you a dense book and says, 'the effect of this spell is that one of the events in this book occurs.' The book contains a whopping 1000 different effects, and what's more, the events have different 'relative probabilities.' The book tells you that the most likely event is 'fireball'; all the probabilities of the other events are described relative to the probability of 'fireball'; for example: on page 155, it says that 'duck storm' is half as likely as 'fireball.'
How are you, the dungeonmaster, to sample a random event from this book? Here's how you can do it:
The accept-reject algorithm:
1) Roll a d1000 to decide a 'candidate' event.
2) Suppose the candidate event is 44% as likely as the most likely event, 'fireball'. Then accept the candidate with probability 44%. (Roll a d100, and accept if the roll is 44 or lower. Otherwise, go back to step 1 until you accept an event.)
3) The accepted event is your random sample.
The accept-reject algorithm is guaranteed to sample from the distribution with the specified relative probabilities.
After much dice rolling you finally end up accepting a candidate: 'summon frog'. You breathe a sigh of relief as you now you can get back to the (routine in comparison) business of handling the battle between the troll-orcs and dragon-elves.
However, not to be outdone, another player decides to cast 'Lv. 2 arcane cyber-effect storm.' For this spell, two different random effects occur: a randomly generated attack, and a randomly generated character buff. The manual for this spell is so huge that it can only fit on a CD. The player boots you up and shows you a page. Your jaw drops: the entry for each attack is about as large a the manual for the previous spell, because it lists a relative probability for each possible accompanying buff
Similarly, the probability of a particular attack spell occurring depends on the probability of the buff occurring.
It would be justified to wonder if a proper probability distribution can even be defined given this information. Well, it turns out that if there is one, it is uniquely specified by the conditional probabilities given in the manual. But how to sample from it?
Luckily for you, the CD comes with an automated Gibbs sample, because you would have to spend an eternity doing the following by hand.
Gibbs sampler algorithm
1) Choose an attack spell randomly
2) Use the accept-reject algorithm to choose the buff conditional on the attack
3) Forget the attack spell you chose in step 1. Choose a new attack spell using the accept-reject algorithm conditional on the buff in step 2
4) Go to step 2, repeat forever (though usually 10000 iterations will be enough)
5) Whatever your algorithm has at the last iteration, is your sample.
You see, in general, MCMC samplers are only asymptotically guaranteed to generate samples from a distribution with the specified conditional probabilities. But in many cases, MCMC samplers are the only practical solution available.
|show 3 more comments|